aboutsummaryrefslogtreecommitdiff
path: root/src/pruning.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/pruning.c')
-rw-r--r--src/pruning.c99
1 files changed, 11 insertions, 88 deletions
diff --git a/src/pruning.c b/src/pruning.c
index 5be977c..2e30351 100644
--- a/src/pruning.c
+++ b/src/pruning.c
@@ -3,13 +3,10 @@
3#include "pruning.h" 3#include "pruning.h"
4 4
5#define ENTRIES_PER_GROUP (2*sizeof(entry_group_t)) 5#define ENTRIES_PER_GROUP (2*sizeof(entry_group_t))
6#define ENTRIES_PER_GROUP_COMPACT (4*sizeof(entry_group_t))
7 6
8static int findchunk(PruneData *pd, int nchunks, uint64_t i); 7static int findchunk(PruneData *pd, int nchunks, uint64_t i);
9static void genptable_bfs(PruneData *pd, int d, int nt, int nc); 8static void genptable_bfs(PruneData *pd, int d, int nt, int nc);
10static void genptable_compress(PruneData *pd);
11static void genptable_fixnasty(PruneData *pd, int d, int nthreads); 9static void genptable_fixnasty(PruneData *pd, int d, int nthreads);
12static void genptable_setbase(PruneData *pd);
13static void * instance_bfs(void *arg); 10static void * instance_bfs(void *arg);
14static void * instance_fixnasty(void *arg); 11static void * instance_fixnasty(void *arg);
15static void ptable_update(PruneData *pd, uint64_t ind, int m); 12static void ptable_update(PruneData *pd, uint64_t ind, int m);
@@ -32,16 +29,13 @@ findchunk(PruneData *pd, int nchunks, uint64_t i)
32PruneData * 29PruneData *
33genptable(PDGenData *pdg, int nthreads) 30genptable(PDGenData *pdg, int nthreads)
34{ 31{
35 bool compact;
36 int d, nchunks, i; 32 int d, nchunks, i;
37 uint64_t oldn, sz; 33 uint64_t oldn;
38 PruneData *pd; 34 PruneData *pd;
39 35
40 for (i = 0; active_pdg[i] != NULL; i++) { 36 for (i = 0; active_pdg[i] != NULL; i++) {
41 pd = active_pdg[i]->pd; 37 pd = active_pdg[i]->pd;
42 if (pd->coord == pdg->coord && 38 if (pd->coord == pdg->coord && pd->moveset == pdg->moveset)
43 pd->moveset == pdg->moveset &&
44 pd->compact == pdg->compact)
45 return pd; 39 return pd;
46 } 40 }
47 41
@@ -49,10 +43,7 @@ genptable(PDGenData *pdg, int nthreads)
49 pdg->pd = pd; 43 pdg->pd = pd;
50 pd->coord = pdg->coord; 44 pd->coord = pdg->coord;
51 pd->moveset = pdg->moveset; 45 pd->moveset = pdg->moveset;
52 pd->compact = pdg->compact; 46 pd->ptable = malloc(ptablesize(pd) * sizeof(entry_group_t));
53
54 sz = ptablesize(pd) * (pd->compact ? 2 : 1);
55 pd->ptable = malloc(sz * sizeof(entry_group_t));
56 47
57 gen_coord(pd->coord); 48 gen_coord(pd->coord);
58 49
@@ -70,11 +61,6 @@ genptable(PDGenData *pdg, int nthreads)
70 ); 61 );
71 } 62 }
72 63
73
74 /* For the first steps we proceed the same way for compact and not */
75 compact = pd->compact;
76 pd->compact = false;
77
78 nchunks = MIN(ptablesize(pd), 100000); 64 nchunks = MIN(ptablesize(pd), 100000);
79 fprintf(stderr, "Generating pt_%s_%s with %d threads\n", 65 fprintf(stderr, "Generating pt_%s_%s with %d threads\n",
80 pd->coord->name, pd->moveset->name, nthreads); 66 pd->coord->name, pd->moveset->name, nthreads);
@@ -102,10 +88,6 @@ genptable(PDGenData *pdg, int nthreads)
102 oldn = pd->n; 88 oldn = pd->n;
103 } 89 }
104 fprintf(stderr, "Pruning table generated!\n"); 90 fprintf(stderr, "Pruning table generated!\n");
105
106 genptable_setbase(pd);
107 if (compact)
108 genptable_compress(pd);
109 91
110 if (!write_ptable_file(pd)) 92 if (!write_ptable_file(pd))
111 fprintf(stderr, "Error writing ptable file\n"); 93 fprintf(stderr, "Error writing ptable file\n");
@@ -115,7 +97,6 @@ genptable_done:
115 active_pdg[i] = malloc(sizeof(PDGenData)); 97 active_pdg[i] = malloc(sizeof(PDGenData));
116 active_pdg[i]->coord = pdg->coord; 98 active_pdg[i]->coord = pdg->coord;
117 active_pdg[i]->moveset = pdg->moveset; 99 active_pdg[i]->moveset = pdg->moveset;
118 active_pdg[i]->compact = pdg->compact;
119 active_pdg[i]->pd = pd; 100 active_pdg[i]->pd = pd;
120 101
121 return pd; 102 return pd;
@@ -156,31 +137,6 @@ genptable_bfs(PruneData *pd, int d, int nthreads, int nchunks)
156} 137}
157 138
158static void 139static void
159genptable_compress(PruneData *pd)
160{
161 int val;
162 uint64_t i, j;
163 entry_group_t mask, v;
164
165 fprintf(stderr, "Compressing table to 2 bits per entry\n");
166
167 for (i = 0; i < pd->coord->max; i += ENTRIES_PER_GROUP_COMPACT) {
168 mask = (entry_group_t)0;
169 for (j = 0; j < ENTRIES_PER_GROUP_COMPACT; j++) {
170 if (i+j >= pd->coord->max)
171 break;
172 val = ptableval(pd, i+j) - pd->base;
173 v = (entry_group_t)MIN(3, MAX(0, val));
174 mask |= v << (2*j);
175 }
176 pd->ptable[i/ENTRIES_PER_GROUP_COMPACT] = mask;
177 }
178
179 pd->compact = true;
180 pd->ptable = realloc(pd->ptable, sizeof(entry_group_t)*ptablesize(pd));
181}
182
183static void
184genptable_fixnasty(PruneData *pd, int d, int nthreads) 140genptable_fixnasty(PruneData *pd, int d, int nthreads)
185{ 141{
186 int i; 142 int i;
@@ -208,22 +164,6 @@ genptable_fixnasty(PruneData *pd, int d, int nthreads)
208 free(upmtx); 164 free(upmtx);
209} 165}
210 166
211static void
212genptable_setbase(PruneData *pd)
213{
214 int i;
215 uint64_t sum, newsum;
216
217 pd->base = 0;
218 sum = pd->count[0] + pd->count[1] + pd->count[2];
219 for (i = 3; i < 16; i++) {
220 newsum = sum + pd->count[i] - pd->count[i-3];
221 if (newsum > sum)
222 pd->base = i-3;
223 sum = newsum;
224 }
225}
226
227static void * 167static void *
228instance_bfs(void *arg) 168instance_bfs(void *arg)
229{ 169{
@@ -317,7 +257,6 @@ print_ptable(PruneData *pd)
317 uint64_t i; 257 uint64_t i;
318 258
319 printf("Table %s_%s\n", pd->coord->name, pd->moveset->name); 259 printf("Table %s_%s\n", pd->coord->name, pd->moveset->name);
320 printf("Base value: %d\n", pd->base);
321 for (i = 0; i < 16; i++) 260 for (i = 0; i < 16; i++)
322 printf("%2" PRIu64 "\t%10" PRIu64 "\n", i, pd->count[i]); 261 printf("%2" PRIu64 "\t%10" PRIu64 "\n", i, pd->count[i]);
323} 262}
@@ -325,11 +264,7 @@ print_ptable(PruneData *pd)
325uint64_t 264uint64_t
326ptablesize(PruneData *pd) 265ptablesize(PruneData *pd)
327{ 266{
328 uint64_t e; 267 return (pd->coord->max + ENTRIES_PER_GROUP - 1) / ENTRIES_PER_GROUP;
329
330 e = pd->compact ? ENTRIES_PER_GROUP_COMPACT : ENTRIES_PER_GROUP;
331
332 return (pd->coord->max + e - 1) / e;
333} 268}
334 269
335static void 270static void
@@ -350,23 +285,11 @@ ptable_update(PruneData *pd, uint64_t ind, int n)
350int 285int
351ptableval(PruneData *pd, uint64_t ind) 286ptableval(PruneData *pd, uint64_t ind)
352{ 287{
353 int sh, ret; 288 int sh;
354 uint64_t e;
355 entry_group_t m;
356
357 if (pd->compact) {
358 e = ENTRIES_PER_GROUP_COMPACT;
359 m = 3;
360 sh = (ind % e) * 2;
361 } else {
362 e = ENTRIES_PER_GROUP;
363 m = 15;
364 sh = (ind % e) * 4;
365 }
366 289
367 ret = (pd->ptable[ind/e] & (m << sh)) >> sh; 290 sh = (ind % ENTRIES_PER_GROUP) * 4;
368 291
369 return pd->compact ? ret + pd->base : ret; 292 return (pd->ptable[ind/ENTRIES_PER_GROUP] & (15 << sh)) >> sh;
370} 293}
371 294
372static bool 295static bool
@@ -376,7 +299,7 @@ read_ptable_file(PruneData *pd)
376 299
377 FILE *f; 300 FILE *f;
378 char fname[strlen(tabledir)+256]; 301 char fname[strlen(tabledir)+256];
379 int i; 302 int i, phony;
380 uint64_t r; 303 uint64_t r;
381 304
382 strcpy(fname, tabledir); 305 strcpy(fname, tabledir);
@@ -388,7 +311,7 @@ read_ptable_file(PruneData *pd)
388 if ((f = fopen(fname, "rb")) == NULL) 311 if ((f = fopen(fname, "rb")) == NULL)
389 return false; 312 return false;
390 313
391 r = fread(&(pd->base), sizeof(int), 1, f); 314 r = fread(&phony, sizeof(int), 1, f);
392 for (i = 0; i < 16; i++) 315 for (i = 0; i < 16; i++)
393 r += fread(&(pd->count[i]), sizeof(uint64_t), 1, f); 316 r += fread(&(pd->count[i]), sizeof(uint64_t), 1, f);
394 r += fread(pd->ptable, sizeof(entry_group_t), ptablesize(pd), f); 317 r += fread(pd->ptable, sizeof(entry_group_t), ptablesize(pd), f);
@@ -405,7 +328,7 @@ write_ptable_file(PruneData *pd)
405 328
406 FILE *f; 329 FILE *f;
407 char fname[strlen(tabledir)+256]; 330 char fname[strlen(tabledir)+256];
408 int i; 331 int i, phony = 0;
409 uint64_t w; 332 uint64_t w;
410 333
411 strcpy(fname, tabledir); 334 strcpy(fname, tabledir);
@@ -417,7 +340,7 @@ write_ptable_file(PruneData *pd)
417 if ((f = fopen(fname, "wb")) == NULL) 340 if ((f = fopen(fname, "wb")) == NULL)
418 return false; 341 return false;
419 342
420 w = fwrite(&(pd->base), sizeof(int), 1, f); 343 w = fwrite(&phony, sizeof(int), 1, f); /* phony replace base */
421 for (i = 0; i < 16; i++) 344 for (i = 0; i < 16; i++)
422 w += fwrite(&(pd->count[i]), sizeof(uint64_t), 1, f); 345 w += fwrite(&(pd->count[i]), sizeof(uint64_t), 1, f);
423 w += fwrite(pd->ptable, sizeof(entry_group_t), ptablesize(pd), f); 346 w += fwrite(pd->ptable, sizeof(entry_group_t), ptablesize(pd), f);

Generated with cgit - Back to sebastiano.tronto.net