From 6f4313bc1ed5be794146e6ca2fd73f48c7906061 Mon Sep 17 00:00:00 2001 From: Sebastiano Tronto Date: Mon, 1 May 2023 12:48:55 +0200 Subject: Reverted to 2.0.3 --- src/pruning.c | 371 +++++++++++++++++++++++++++++++++++++++------------------- 1 file changed, 252 insertions(+), 119 deletions(-) (limited to 'src/pruning.c') diff --git a/src/pruning.c b/src/pruning.c index 3cc9152..1dba949 100644 --- a/src/pruning.c +++ b/src/pruning.c @@ -1,5 +1,3 @@ -#define PRUNING_C - #include "pruning.h" #define ENTRIES_PER_GROUP (2*sizeof(entry_group_t)) @@ -7,14 +5,106 @@ static int findchunk(PruneData *pd, int nchunks, uint64_t i); static void genptable_bfs(PruneData *pd, int d, int nt, int nc); +static void genptable_compress(PruneData *pd); static void genptable_fixnasty(PruneData *pd, int d, int nthreads); +static void genptable_setbase(PruneData *pd); static void * instance_bfs(void *arg); static void * instance_fixnasty(void *arg); -static void ptable_update(PruneData *pd, uint64_t ind, int m); +static void ptable_update(PruneData *pd, Cube cube, int m); +static void ptable_update_index(PruneData *pd, uint64_t ind, int m); +static int ptableval_index(PruneData *pd, uint64_t ind); static bool read_ptable_file(PruneData *pd); static bool write_ptable_file(PruneData *pd); -PruneData *active_pd[256]; +PruneData +pd_eofb_HTM = { + .filename = "pt_eofb_HTM", + .coord = &coord_eofb, + .moveset = &moveset_HTM, +}; + +PruneData +pd_coud_HTM = { + .filename = "pt_coud_HTM", + .coord = &coord_coud, + .moveset = &moveset_HTM, +}; + +PruneData +pd_cornershtr_HTM = { + .filename = "pt_cornershtr_HTM", + .coord = &coord_cornershtr, + .moveset = &moveset_HTM, +}; + +PruneData +pd_corners_HTM = { + .filename = "pt_corners_HTM", + .coord = &coord_corners, + .moveset = &moveset_HTM, +}; + +PruneData +pd_drud_sym16_HTM = { + .filename = "pt_drud_sym16_HTM", + .coord = &coord_drud_sym16, + .moveset = &moveset_HTM, +}; + +PruneData +pd_drud_eofb = { + .filename = "pt_drud_eofb", + .coord = &coord_drud_eofb, + .moveset = &moveset_eofb, +}; + +PruneData +pd_drudfin_noE_sym16_drud = { + .filename = "pt_drudfin_noE_sym16_drud", + .coord = &coord_drudfin_noE_sym16, + .moveset = &moveset_drud, +}; + +PruneData +pd_htr_drud = { + .filename = "pt_htr_drud", + .coord = &coord_htr_drud, + .moveset = &moveset_drud, +}; + +PruneData +pd_htrfin_htr = { + .filename = "pt_htrfin_htr", + .coord = &coord_htrfin, + .moveset = &moveset_htr, +}; + +PruneData +pd_nxopt31_HTM = { + .filename = "pt_nxopt31_HTM", + .coord = &coord_nxopt31, + .moveset = &moveset_HTM, + + .compact = true, + .fallback = &pd_drud_sym16_HTM, + .fbmod = BINOM8ON4, +}; + +PruneData * all_pd[] = { + &pd_eofb_HTM, + &pd_coud_HTM, + &pd_cornershtr_HTM, + &pd_corners_HTM, + &pd_drud_sym16_HTM, + &pd_drud_eofb, + &pd_drudfin_noE_sym16_drud, + &pd_htr_drud, + &pd_htrfin_htr, + &pd_nxopt31_HTM, + NULL +}; + +/* Functions *****************************************************************/ int findchunk(PruneData *pd, int nchunks, uint64_t i) @@ -27,47 +117,59 @@ findchunk(PruneData *pd, int nchunks, uint64_t i) return MIN(nchunks-1, (int)(i / chunksize)); } -PruneData * +void +free_pd(PruneData *pd) +{ + if (pd->generated) + free(pd->ptable); + + pd->generated = false; +} + +void genptable(PruneData *pd, int nthreads) { - int d, nchunks, i, maxv; - uint64_t oldn; - - for (i = 0; active_pd[i] != NULL; i++) { - if (active_pd[i]->coord == pd->coord && - active_pd[i]->moveset == pd->moveset && - active_pd[i]->compact == pd->compact) - return active_pd[i]; - } + bool compact; + int d, nchunks; + uint64_t oldn, sz; - init_moveset(pd->moveset); - gen_coord(pd->coord); + if (pd->generated) + return; - pd->ptable = malloc(ptablesize(pd) * sizeof(entry_group_t)); + /* TODO: check if memory is enough, otherwise maybe exit gracefully? */ + sz = ptablesize(pd) * (pd->compact ? 2 : 1); + pd->ptable = malloc(sz * sizeof(entry_group_t)); - if (read_ptable_file(pd)) - goto genptable_done; + if (read_ptable_file(pd)) { + pd->generated = true; + return; + } if (nthreads < 4) { fprintf(stderr, "--- Warning ---\n" "You are using only %d threads to generate the pruning" - "tables. This can take a while.\n" + "tables. This can take a while." "Unless you did this intentionally, you should re-run" "this command with `-t 4' or more.\n" "---------------\n\n", nthreads ); } + + /* For the first steps we proceed the same way for compact and not */ + compact = pd->compact; + pd->compact = false; + pd->generated = true; + nchunks = MIN(ptablesize(pd), 100000); - fprintf(stderr, "Generating pt_%s_%s with %d threads\n", - pd->coord->name, pd->moveset->name, nthreads); + fprintf(stderr, "Cannot load %s, generating it with %d threads\n", + pd->filename, nthreads); + memset(pd->ptable, ~(uint8_t)0, ptablesize(pd)*sizeof(entry_group_t)); - for (i = 0; i < 16; i++) - pd->count[i] = 0; - ptable_update(pd, 0, 0); + ptable_update(pd, (Cube){0}, 0); pd->n = 1; oldn = 0; genptable_fixnasty(pd, 0, nthreads); @@ -76,9 +178,7 @@ genptable(PruneData *pd, int nthreads) 0, pd->n - oldn, pd->n, pd->coord->max); oldn = pd->n; pd->count[0] = pd->n; - - maxv = pd->compact ? MIN(15, pd->base + 4) : 15; - for (d = 0; d < maxv && pd->n < pd->coord->max; d++) { + for (d = 0; d < 15 && pd->n < pd->coord->max; d++) { genptable_bfs(pd, d, nthreads, nchunks); genptable_fixnasty(pd, d+1, nthreads); fprintf(stderr, "Depth %d done, generated %" @@ -87,17 +187,14 @@ genptable(PruneData *pd, int nthreads) pd->count[d+1] = pd->n - oldn; oldn = pd->n; } - if (pd->compact) - fprintf(stderr, "Compact table, values above " - "%d are inaccurate.\n", maxv-1); fprintf(stderr, "Pruning table generated!\n"); - + + genptable_setbase(pd); + if (compact) + genptable_compress(pd); + if (!write_ptable_file(pd)) fprintf(stderr, "Error writing ptable file\n"); - -genptable_done: - for (i = 0; active_pd[i] != NULL; i++); - return active_pd[i] = pd; } static void @@ -134,6 +231,31 @@ genptable_bfs(PruneData *pd, int d, int nthreads, int nchunks) free(mtx[i]); } +static void +genptable_compress(PruneData *pd) +{ + int val; + uint64_t i, j; + entry_group_t mask, v; + + fprintf(stderr, "Compressing table to 2 bits per entry\n"); + + for (i = 0; i < pd->coord->max; i += ENTRIES_PER_GROUP_COMPACT) { + mask = (entry_group_t)0; + for (j = 0; j < ENTRIES_PER_GROUP_COMPACT; j++) { + if (i+j >= pd->coord->max) + break; + val = ptableval_index(pd, i+j) - pd->base; + v = (entry_group_t)MIN(3, MAX(0, val)); + mask |= v << (2*j); + } + pd->ptable[i/ENTRIES_PER_GROUP_COMPACT] = mask; + } + + pd->compact = true; + pd->ptable = realloc(pd->ptable, sizeof(entry_group_t)*ptablesize(pd)); +} + static void genptable_fixnasty(PruneData *pd, int d, int nthreads) { @@ -142,7 +264,7 @@ genptable_fixnasty(PruneData *pd, int d, int nthreads) ThreadDataGenpt td[nthreads]; pthread_mutex_t *upmtx; - if (pd->coord->type != SYMCOMP_COORD) + if (pd->coord->tfind == NULL) return; upmtx = malloc(sizeof(pthread_mutex_t)); @@ -162,12 +284,28 @@ genptable_fixnasty(PruneData *pd, int d, int nthreads) free(upmtx); } +static void +genptable_setbase(PruneData *pd) +{ + int i; + uint64_t sum, newsum; + + pd->base = 0; + sum = pd->count[0] + pd->count[1] + pd->count[2]; + for (i = 3; i < 16; i++) { + newsum = sum + pd->count[i] - pd->count[i-3]; + if (newsum > sum) + pd->base = i-3; + sum = newsum; + } +} + static void * instance_bfs(void *arg) { ThreadDataGenpt *td; uint64_t i, ii, blocksize, rmin, rmax, updated; - int j, pval, ichunk, oldc, newc; + int j, pval, ichunk; Move *ms; td = (ThreadDataGenpt *)arg; @@ -178,43 +316,25 @@ instance_bfs(void *arg) td->pd->coord->max : ((uint64_t)td->thid + 1) * blocksize; - if (td->pd->compact) { - if (td->d <= td->pd->base) { - oldc = 1; - newc = 1; - } else { - oldc = td->d - td->pd->base; - newc = td->d - td->pd->base; - } - } else { - oldc = td->d; - newc = td->d + 1; - } - updated = 0; for (i = rmin; i < rmax; i++) { ichunk = findchunk(td->pd, td->nchunks, i); pthread_mutex_lock(td->mutex[ichunk]); - pval = ptableval(td->pd, i); + pval = ptableval_index(td->pd, i); pthread_mutex_unlock(td->mutex[ichunk]); - if (pval == oldc) { + if (pval == td->d) { for (j = 0; ms[j] != NULLMOVE; j++) { - ii = move_coord(td->pd->coord, ms[j], i, NULL); + ii = td->pd->coord->move(ms[j], i); ichunk = findchunk(td->pd, td->nchunks, ii); pthread_mutex_lock(td->mutex[ichunk]); - pval = ptableval(td->pd, ii); - if (pval > newc) { - ptable_update(td->pd, ii, newc); + pval = ptableval_index(td->pd, ii); + if (pval > td->d+1) { + ptable_update_index(td->pd, + ii, td->d+1); updated++; } pthread_mutex_unlock(td->mutex[ichunk]); } - if (td->pd->compact && td->d <= td->pd->base) { - ichunk = findchunk(td->pd, td->nchunks, i); - pthread_mutex_lock(td->mutex[ichunk]); - ptable_update(td->pd, i, 0); - pthread_mutex_unlock(td->mutex[ichunk]); - } } } @@ -229,40 +349,30 @@ static void * instance_fixnasty(void *arg) { ThreadDataGenpt *td; - uint64_t i, ii, blocksize, rmin, rmax, updated, ss, M; - int j, oldc; - Trans t; + uint64_t i, ii, nb, blocksize, rmin, rmax, updated; + int j, n; + Trans t, aux[NTRANS]; td = (ThreadDataGenpt *)arg; - - /* We know type = SYMCOMP_COORD */ - M = td->pd->coord->base[1]->max; - blocksize = (td->pd->coord->base[0]->max / td->nthreads) * M; + nb = td->pd->coord->max / td->pd->coord->base->max; + blocksize = (td->pd->coord->base->max / td->nthreads) * nb; rmin = ((uint64_t)td->thid) * blocksize; rmax = td->thid == td->nthreads - 1 ? td->pd->coord->max : ((uint64_t)td->thid + 1) * blocksize; - if (td->pd->compact) { - if (td->d <= td->pd->base) - oldc = 1; - else - oldc = td->d - td->pd->base; - } else { - oldc = td->d; - } - updated = 0; for (i = rmin; i < rmax; i++) { - if (ptableval(td->pd, i) == oldc) { - ss = td->pd->coord->base[0]->selfsim[i/M]; - for (j = 0; j < td->pd->coord->base[0]->tgrp->n; j++) { - t = td->pd->coord->base[0]->tgrp->t[j]; - if (t == uf || !(ss & ((uint64_t)1<pd, i) == td->d) { + if ((n = td->pd->coord->tfind(i, aux)) == 1) + continue; + + for (j = 0; j < n; j++) { + if ((t = aux[j]) == uf) continue; - ii = trans_coord(td->pd->coord, t, i); - if (ptableval(td->pd, ii) > oldc) { - ptable_update(td->pd, ii, oldc); + ii = td->pd->coord->transform(t, i); + if (ptableval_index(td->pd, ii) > td->d) { + ptable_update_index(td->pd, ii, td->d); updated++; } } @@ -281,13 +391,11 @@ print_ptable(PruneData *pd) { uint64_t i; - printf("Table %s_%s\n", pd->coord->name, pd->moveset->name); - - if (pd->compact) { - printf("Compract table with base value: %d\n", pd->base); - printf("Values above %d are inaccurate.\n", pd->base + 3); - } - + if (!pd->generated) + genptable(pd, 1); /* TODO: set default nthreads somewhere */ + + printf("Table %s\n", pd->filename); + printf("Base value: %d\n", pd->base); for (i = 0; i < 16; i++) printf("%2" PRIu64 "\t%10" PRIu64 "\n", i, pd->count[i]); } @@ -303,31 +411,48 @@ ptablesize(PruneData *pd) } static void -ptable_update(PruneData *pd, uint64_t ind, int n) +ptable_update(PruneData *pd, Cube cube, int n) { - int sh; - entry_group_t f, mask; - uint64_t i, e, b; + ptable_update_index(pd, pd->coord->index(cube), n); +} - e = pd->compact ? ENTRIES_PER_GROUP_COMPACT : ENTRIES_PER_GROUP; - b = pd->compact ? 2 : 4; - f = pd->compact ? 3 : 15; +static void +ptable_update_index(PruneData *pd, uint64_t ind, int n) +{ + int sh; + entry_group_t mask; + uint64_t i; - sh = b * (ind % e); - mask = f << sh; - i = ind / e; + sh = 4 * (ind % ENTRIES_PER_GROUP); + mask = ((entry_group_t)15) << sh; + i = ind/ENTRIES_PER_GROUP; pd->ptable[i] &= ~mask; - pd->ptable[i] |= (((entry_group_t)n) & f) << sh; + pd->ptable[i] |= (((entry_group_t)n)&15) << sh; } int -ptableval(PruneData *pd, uint64_t ind) +ptableval(PruneData *pd, Cube cube) { - int sh; - uint64_t e; + return ptableval_index(pd, pd->coord->index(cube)); +} + +static int +ptableval_index(PruneData *pd, uint64_t ind) +{ + int sh, ret; + entry_group_t mask; + uint64_t i, e; entry_group_t m; + if (!pd->generated) { + fprintf(stderr, "Warning: request pruning table value" + " for uninitialized table %s.\n It's fine, but it" + " should not happen. Please report bug.\n", + pd->filename); + genptable(pd, 1); /* TODO: set default or remove this case */ + } + if (pd->compact) { e = ENTRIES_PER_GROUP_COMPACT; m = 3; @@ -338,7 +463,19 @@ ptableval(PruneData *pd, uint64_t ind) sh = (ind % e) * 4; } - return (pd->ptable[ind/e] & (m << sh)) >> sh; + mask = m << sh; + i = ind/e; + + ret = (pd->ptable[i] & mask) >> sh; + + if (pd->compact) { + if (ret) + ret += pd->base; + else + ret = ptableval_index(pd->fallback, ind / pd->fbmod); + } + + return ret; } static bool @@ -347,15 +484,13 @@ read_ptable_file(PruneData *pd) init_env(); FILE *f; - char fname[strlen(tabledir)+256]; + char fname[strlen(tabledir)+100]; int i; uint64_t r; strcpy(fname, tabledir); - strcat(fname, "/pt_"); - strcat(fname, pd->coord->name); - strcat(fname, "_"); - strcat(fname, pd->moveset->name); + strcat(fname, "/"); + strcat(fname, pd->filename); if ((f = fopen(fname, "rb")) == NULL) return false; @@ -376,15 +511,13 @@ write_ptable_file(PruneData *pd) init_env(); FILE *f; - char fname[strlen(tabledir)+256]; + char fname[strlen(tabledir)+100]; int i; uint64_t w; strcpy(fname, tabledir); - strcat(fname, "/pt_"); - strcat(fname, pd->coord->name); - strcat(fname, "_"); - strcat(fname, pd->moveset->name); + strcat(fname, "/"); + strcat(fname, pd->filename); if ((f = fopen(fname, "wb")) == NULL) return false; -- cgit v1.3