From 2f924f942bd6e7126e8f1d8692e475c95bd9fe82 Mon Sep 17 00:00:00 2001 From: Sebastiano Tronto Date: Thu, 16 Dec 2021 19:25:58 +0100 Subject: Added a new pruning table (equivalent to nxopt31). I have not tested it yet, it takes a while to generate. Plus I have done a whole lot of refactoring in random places because I cannot focus on one thing at the time. --- src/pruning.c | 95 ++++++++++++++++++++++++++++++++--------------------------- 1 file changed, 52 insertions(+), 43 deletions(-) (limited to 'src/pruning.c') diff --git a/src/pruning.c b/src/pruning.c index b305a89..0a6e305 100644 --- a/src/pruning.c +++ b/src/pruning.c @@ -1,11 +1,10 @@ #include "pruning.h" -/* Chunks for multithreading */ -/* TODO: try smaller */ -#define NCHUNKS 100000 +#define NCHUNKS 100000 +#define ENTRIES_PER_GROUP (2*sizeof(entry_group_t)) static int findchunk(PruneData *pd, int nchunks, uint64_t i); -static void genptable_bfs(PruneData *pd,int d,Move *ms,int nt,int nc); +static void genptable_bfs(PruneData *pd, int d, int nt, int nc); static void genptable_fixnasty(PruneData *pd, int d); static void * instance_bfs(void *arg); static void ptable_update(PruneData *pd, Cube cube, int m); @@ -18,70 +17,77 @@ PruneData pd_eofb_HTM = { .filename = "pt_eofb_HTM", .coord = &coord_eofb, - .moveset = moveset_HTM, + .moveset = &moveset_HTM, }; PruneData pd_coud_HTM = { .filename = "pt_coud_HTM", .coord = &coord_coud, - .moveset = moveset_HTM, + .moveset = &moveset_HTM, }; PruneData pd_cornershtr_HTM = { .filename = "pt_cornershtr_HTM", .coord = &coord_cornershtr, - .moveset = moveset_HTM, + .moveset = &moveset_HTM, }; PruneData pd_corners_HTM = { .filename = "pt_corners_HTM", .coord = &coord_corners, - .moveset = moveset_HTM, + .moveset = &moveset_HTM, }; PruneData pd_drud_sym16_HTM = { .filename = "pt_drud_sym16_HTM", .coord = &coord_drud_sym16, - .moveset = moveset_HTM, + .moveset = &moveset_HTM, }; PruneData pd_drud_eofb = { .filename = "pt_drud_eofb", .coord = &coord_drud_eofb, - .moveset = moveset_eofb, + .moveset = &moveset_eofb, }; PruneData pd_drudfin_noE_sym16_drud = { .filename = "pt_drudfin_noE_sym16_drud", .coord = &coord_drudfin_noE_sym16, - .moveset = moveset_drud, + .moveset = &moveset_drud, }; PruneData pd_htr_drud = { .filename = "pt_htr_drud", .coord = &coord_htr_drud, - .moveset = moveset_drud, + .moveset = &moveset_drud, }; PruneData pd_htrfin_htr = { .filename = "pt_htrfin_htr", .coord = &coord_htrfin, - .moveset = moveset_htr, + .moveset = &moveset_htr, }; PruneData pd_khuge_HTM = { .filename = "pt_khuge_HTM", .coord = &coord_khuge, - .moveset = moveset_HTM, + .moveset = &moveset_HTM, +}; + +PruneData +pd_nxopt31_HTM = { + .filename = "pt_nxopt31_HTM", + .coord = &coord_nxopt31, + .moveset = &moveset_HTM, }; PruneData * allpd[NPTABLES] = { @@ -95,6 +101,7 @@ PruneData * allpd[NPTABLES] = { &pd_htr_drud, &pd_htrfin_htr, &pd_khuge_HTM, + &pd_nxopt31_HTM, }; /* Functions *****************************************************************/ @@ -105,8 +112,7 @@ findchunk(PruneData *pd, int nchunks, uint64_t i) uint64_t chunksize; chunksize = pd->coord->max / (uint64_t)nchunks; - if (chunksize % 2 != 0) - chunksize++; + chunksize += ENTRIES_PER_GROUP - (chunksize % ENTRIES_PER_GROUP); return MIN(nchunks-1, (int)(i / chunksize)); } @@ -114,15 +120,14 @@ findchunk(PruneData *pd, int nchunks, uint64_t i) void genptable(PruneData *pd, int nthreads) { - Move *ms; int d, nchunks; - uint64_t j, oldn; + uint64_t oldn; if (pd->generated) return; /* TODO: check if memory is enough, otherwise maybe exit gracefully? */ - pd->ptable = malloc(ptablesize(pd) * sizeof(uint8_t)); + pd->ptable = malloc(ptablesize(pd) * sizeof(entry_group_t)); if (read_ptable_file(pd)) { pd->generated = true; @@ -130,17 +135,12 @@ genptable(PruneData *pd, int nthreads) } pd->generated = true; - nchunks = MIN(pd->coord->max/2, NCHUNKS); + nchunks = MIN(pd->coord->max/ENTRIES_PER_GROUP, NCHUNKS); fprintf(stderr, "Cannot load %s, generating it " "with %d threads and %d chunks\n", pd->filename, nthreads, nchunks); - ms = malloc(NMOVES * sizeof(Move)); - moveset_to_list(pd->moveset, ms); - - /* We use 4 bits per value, so any distance >= 15 is set to 15 */ - for (j = 0; j < pd->coord->max; j++) - ptable_update_index(pd, j, 15); + memset(pd->ptable, ~(uint8_t)0, ptablesize(pd)*sizeof(entry_group_t)); ptable_update(pd, (Cube){0}, 0); pd->n = 1; @@ -151,7 +151,7 @@ genptable(PruneData *pd, int nthreads) 0, pd->n - oldn, pd->n, pd->coord->max); oldn = pd->n; for (d = 0; d < 15 && pd->n < pd->coord->max; d++) { - genptable_bfs(pd, d, ms, nthreads, nchunks); + genptable_bfs(pd, d, nthreads, nchunks); genptable_fixnasty(pd, d+1); fprintf(stderr, "Depth %d done, generated %" PRIu64 "\t(%" PRIu64 "/%" PRIu64 ")\n", @@ -162,12 +162,10 @@ genptable(PruneData *pd, int nthreads) if (!write_ptable_file(pd)) fprintf(stderr, "Error writing ptable file\n"); - - free(ms); } static void -genptable_bfs(PruneData *pd, int d, Move *ms, int nthreads, int nchunks) +genptable_bfs(PruneData *pd, int d, int nthreads, int nchunks) { int i; pthread_t t[nthreads]; @@ -186,7 +184,6 @@ genptable_bfs(PruneData *pd, int d, Move *ms, int nthreads, int nchunks) td[i].nthreads = nthreads; td[i].pd = pd; td[i].d = d; - td[i].ms = ms; td[i].nchunks = nchunks; td[i].mutex = mtx; td[i].upmutex = upmtx; @@ -237,8 +234,10 @@ instance_bfs(void *arg) uint64_t i, ii, blocksize, rmin, rmax, updated; int j, pval, ichunk; Cube c, cc; + Move *ms; td = (ThreadDataGenpt *)arg; + ms = td->pd->moveset->sorted_moves; blocksize = td->pd->coord->max / (uint64_t)td->nthreads; rmin = ((uint64_t)td->thid) * blocksize; rmax = td->thid == td->nthreads - 1 ? @@ -253,8 +252,8 @@ instance_bfs(void *arg) pthread_mutex_unlock(td->mutex[ichunk]); if (pval == td->d) { c = td->pd->coord->cube(i); - for (j = 0; td->ms[j] != NULLMOVE; j++) { - cc = apply_move(td->ms[j], c); + for (j = 0; ms[j] != NULLMOVE; j++) { + cc = apply_move(ms[j], c); ii = td->pd->coord->index(cc); ichunk = findchunk(td->pd, td->nchunks, ii); pthread_mutex_lock(td->mutex[ichunk]); @@ -296,7 +295,7 @@ print_ptable(PruneData *pd) uint64_t ptablesize(PruneData *pd) { - return (pd->coord->max + 1) / 2; + return (pd->coord->max + ENTRIES_PER_GROUP - 1) / ENTRIES_PER_GROUP; } static void @@ -308,14 +307,16 @@ ptable_update(PruneData *pd, Cube cube, int n) static void ptable_update_index(PruneData *pd, uint64_t ind, int n) { - uint8_t oldval2; - int other; + int sh; + entry_group_t mask; + uint64_t i; - oldval2 = pd->ptable[ind/2]; - other = (ind % 2) ? oldval2 % 16 : oldval2 / 16; + sh = 4 * (ind % ENTRIES_PER_GROUP); + mask = ((entry_group_t)15) << sh; + i = ind/ENTRIES_PER_GROUP; - pd->ptable[ind/2] = (ind % 2) ? 16*n + other : 16*other + n; - /*pd->n++;*/ + pd->ptable[i] &= ~mask; + pd->ptable[i] |= (((entry_group_t)n)&15) << sh; } int @@ -327,6 +328,10 @@ ptableval(PruneData *pd, Cube cube) static int ptableval_index(PruneData *pd, uint64_t ind) { + int sh; + entry_group_t mask; + uint64_t i; + if (!pd->generated) { fprintf(stderr, "Warning: request pruning table value" " for uninitialized table %s.\n It's fine, but it" @@ -335,7 +340,11 @@ ptableval_index(PruneData *pd, uint64_t ind) genptable(pd, 1); /* TODO: set default or remove this case */ } - return (ind % 2) ? pd->ptable[ind/2] / 16 : pd->ptable[ind/2] % 16; + sh = 4 * (ind % ENTRIES_PER_GROUP); + mask = ((entry_group_t)15) << sh; + i = ind/ENTRIES_PER_GROUP; + + return (pd->ptable[i] & mask) >> sh; } static bool @@ -354,7 +363,7 @@ read_ptable_file(PruneData *pd) if ((f = fopen(fname, "rb")) == NULL) return false; - r = fread(pd->ptable, sizeof(uint8_t), ptablesize(pd), f); + r = fread(pd->ptable, sizeof(entry_group_t), ptablesize(pd), f); fclose(f); return r == ptablesize(pd); @@ -376,7 +385,7 @@ write_ptable_file(PruneData *pd) if ((f = fopen(fname, "wb")) == NULL) return false; - written = fwrite(pd->ptable, sizeof(uint8_t), ptablesize(pd), f); + written = fwrite(pd->ptable, sizeof(entry_group_t), ptablesize(pd), f); fclose(f); return written == ptablesize(pd); -- cgit v1.3