From 5727f06c5694a4831881322876e3ba4d8ce3b743 Mon Sep 17 00:00:00 2001 From: Sebastiano Tronto Date: Sat, 20 Jul 2024 10:05:51 +0200 Subject: Finally fixed selfsim logic --- TODO.txt | 9 +- src/solve_h48.h | 117 ++++---- test/111_gendata_h48_h0/00_h_0.in | 0 test/111_gendata_h48_h0/00_h_0.out | 23 -- test/111_gendata_h48_h0/gendata_h48_tests.c | 33 --- test/111_h48map/00_small.in | 11 + test/111_h48map/00_small.out | 3 + test/111_h48map/01_large.in | 303 +++++++++++++++++++++ test/111_h48map/01_large.out | 83 ++++++ test/111_h48map/h48map_tests.c | 83 ++++++ test/112_gendata_h48/00_h_0.in | 2 + test/112_gendata_h48/00_h_0.out | 23 ++ test/112_gendata_h48/gendata_h48_tests.c | 43 +++ test/112_h48map/00_small.in | 11 - test/112_h48map/00_small.out | 3 - test/112_h48map/01_large.in | 303 --------------------- test/112_h48map/01_large.out | 83 ------ test/112_h48map/h48map_tests.c | 83 ------ tools/01_gendata_h48/benchmark_gendata_h48.c | 47 ++++ tools/02_stats_tables_h48/stats_tables_h48.c | 152 +++++++++++ .../benchmark_gendata_h48/benchmark_gendata_h48.c | 47 ---- tools/stats_tables_h48/stats_tables_h48.c | 152 ----------- 22 files changed, 817 insertions(+), 797 deletions(-) delete mode 100644 test/111_gendata_h48_h0/00_h_0.in delete mode 100644 test/111_gendata_h48_h0/00_h_0.out delete mode 100644 test/111_gendata_h48_h0/gendata_h48_tests.c create mode 100644 test/111_h48map/00_small.in create mode 100644 test/111_h48map/00_small.out create mode 100644 test/111_h48map/01_large.in create mode 100644 test/111_h48map/01_large.out create mode 100644 test/111_h48map/h48map_tests.c create mode 100644 test/112_gendata_h48/00_h_0.in create mode 100644 test/112_gendata_h48/00_h_0.out create mode 100644 test/112_gendata_h48/gendata_h48_tests.c delete mode 100644 test/112_h48map/00_small.in delete mode 100644 test/112_h48map/00_small.out delete mode 100644 test/112_h48map/01_large.in delete mode 100644 test/112_h48map/01_large.out delete mode 100644 test/112_h48map/h48map_tests.c create mode 100644 tools/01_gendata_h48/benchmark_gendata_h48.c create mode 100644 tools/02_stats_tables_h48/stats_tables_h48.c delete mode 100644 tools/benchmark_gendata_h48/benchmark_gendata_h48.c delete mode 100644 tools/stats_tables_h48/stats_tables_h48.c diff --git a/TODO.txt b/TODO.txt index a52945f..b164e23 100644 --- a/TODO.txt +++ b/TODO.txt @@ -1,4 +1,7 @@ -Bug in esep table generation +H48 table generation + - fix gendata tool + - use to test generation of full h0k4 table + - remove ifdef and old code - compute all tables for h<11 x compute visited up to a fixed depth 8 - compute additional step (if needed) to fill <=base @@ -10,9 +13,7 @@ Bug in esep table generation - Add long-running test for h0k4 (maybe as a tool?) - tests for other sizes? - optimize - - use cached values for invcoord_esep? check if it is faster - - Unify and improve performance of finding nasty sim - (right now we don't even use selfsim) + - use only transform_edges (need compose trans) - parallelize with pthread (OLD: diff --git a/src/solve_h48.h b/src/solve_h48.h index ad77156..ad865a7 100644 --- a/src/solve_h48.h +++ b/src/solve_h48.h @@ -27,6 +27,24 @@ #define MAX_SOLUTION_LENGTH 20 +/* +TODO: This loop other similar h48 coordinates can be improved by only +transforming edges, but we need to compose transformations (i.e. conjugate +_t by _ttrep). +*/ +#define _foreach_h48sim(_cube, _cocsepdata, _selfsim, _h, _action) \ + int64_t _cocsep = coord_cocsep(_cube); \ + uint8_t _ttrep = TTREP(_cocsepdata[_cocsep]); \ + int64_t _coclass = COCLASS(_cocsepdata[_cocsep]); \ + cube_t _rep = transform(_cube, _ttrep); \ + uint64_t _sim = _selfsim[_coclass]; \ + for (uint8_t _t = 0; _t < 48 && _sim; _t++, _sim >>= 1) { \ + if (!(_sim & 1)) continue; \ + _cube = transform(_rep, _t); \ + _cube = transform(_cube, inverse_trans(_ttrep)); \ + _action \ + } + typedef struct { uint64_t n; uint64_t capacity; @@ -229,12 +247,12 @@ coord_h48(cube_t c, const uint32_t *cocsepdata, uint8_t h) } _static_inline int64_t -coord_h48_edges(cube_t c, int64_t coclass, uint8_t t, uint8_t h) +coord_h48_edges(cube_t c, int64_t coclass, uint8_t ttrep, uint8_t h) { cube_t d; int64_t esep, eo, edges; - d = transform_edges(c, t); + d = transform_edges(c, ttrep); esep = coord_esep(d); eo = coord_eo(d); edges = (esep << 11) + eo; @@ -394,11 +412,11 @@ gen_h48short( const uint64_t *selfsim, h48map_t *map ) { - uint8_t i, m, t; - int64_t coord, cc; - uint64_t j, oldn, sim; + uint8_t i, m; + int64_t coord; + uint64_t j, oldn; kvpair_t kv; - cube_t cube, d, e; + cube_t cube, d; cube = solvedcube(); coord = coord_h48(cube, cocsepdata, 11); @@ -418,17 +436,10 @@ gen_h48short( cube = invcoord_h48(kv.key, crep, 11); for (m = 0; m < 18; m++) { d = move(cube, m); - coord = coord_h48(d, cocsepdata, 11); - h48map_insertmin(map, coord, i+1); - cc = coord / H48_ESIZE(11); - sim = selfsim[cc] >> UINT64_C(1); - for (t = 1; t < 48 && sim; t++) { - /* TODO: optimize by using transform_edges, - corner coordinate is kept */ - e = transform(d, t); - coord = coord_h48(e, cocsepdata, 11); + _foreach_h48sim(d, cocsepdata, selfsim, 11, + coord = coord_h48(d, cocsepdata, 11); h48map_insertmin(map, coord, i+1); - } + ) } } LOG("found %" PRIu8 "\n", map->n-oldn); @@ -512,9 +523,8 @@ gendata_h48h0k4_bfs_fromdone(bfsarg_esep_t *arg) { uint8_t c, m, x; uint32_t cc; - int64_t i, j, k, t, cocsep_coord; - uint64_t sim; - cube_t cube, moved, transd; + int64_t i, j, k; + cube_t cube, moved; for (i = 0, cc = 0; i < (int64_t)ESEP_MAX(0); i++) { c = get_esep_pval(arg->buf32, i); @@ -522,30 +532,16 @@ gendata_h48h0k4_bfs_fromdone(bfsarg_esep_t *arg) continue; cube = invcoord_h48(i, arg->crep, 0); for (m = 0; m < 18; m++) { - /* - * TODO: here we can optimize by computing at first - * only the corner part of the coordinate, and then - * the edge parts for each transformation. - */ moved = move(cube, m); j = coord_h48(moved, arg->cocsepdata, 0); - x = get_esep_pval(arg->buf32, j); - if (x <= arg->depth) + if (get_esep_pval(arg->buf32, j) <= arg->depth) continue; - set_esep_pval(arg->buf32, j, arg->depth); - cc += x != arg->depth; - cocsep_coord = j / H48_ESIZE(0); - sim = arg->selfsim[cocsep_coord] >> UINT64_C(1); - for (t = 1; t < 48 && sim; t++) { - /* TODO: use only selfsim */ - transd = transform(moved, t); - k = coord_h48(transd, arg->cocsepdata, 0); + _foreach_h48sim(moved, arg->cocsepdata, arg->selfsim, 0, + k = coord_h48(moved, arg->cocsepdata, 0); x = get_esep_pval(arg->buf32, k); - if (x <= arg->depth) - continue; set_esep_pval(arg->buf32, k, arg->depth); cc += x != arg->depth; - } + ) } } @@ -557,8 +553,8 @@ gendata_h48h0k4_bfs_fromnew(bfsarg_esep_t *arg) { uint8_t c, m, x; uint32_t cc; - int64_t i, j, t, cocsep_coord, sim; - cube_t cube, moved, transd; + int64_t i, j; + cube_t cube, moved; for (i = 0, cc = 0; i < (int64_t)ESEP_MAX(0); i++) { c = get_esep_pval(arg->buf32, i); @@ -569,22 +565,33 @@ gendata_h48h0k4_bfs_fromnew(bfsarg_esep_t *arg) moved = move(cube, m); j = coord_h48(moved, arg->cocsepdata, 0); x = get_esep_pval(arg->buf32, j); - if (x < arg->depth) - goto neighbor_found; - } - continue; -neighbor_found: - set_esep_pval(arg->buf32, i, arg->depth); - cc++; - cocsep_coord = i / H48_ESIZE(0); - sim = arg->selfsim[cocsep_coord] >> 1; - for (t = 1; t < 48 && sim; t++) { - /* TODO: use only selfsim */ - transd = transform(cube, t); - j = coord_h48(transd, arg->cocsepdata, 0); - x = get_esep_pval(arg->buf32, j); - set_esep_pval(arg->buf32, j, arg->depth); - cc += x == 0xF; + if (x >= arg->depth) + continue; +#if 0 + cube_t transd; + int64_t t, cocsep_coord, sim; + + set_esep_pval(arg->buf32, i, arg->depth); + cc++; + cocsep_coord = i / H48_ESIZE(0); + sim = arg->selfsim[cocsep_coord] >> 1; + for (t = 1; t < 48 && sim; t++) { + transd = transform(cube, t); + j = coord_h48(transd, arg->cocsepdata, 0); + x = get_esep_pval(arg->buf32, j); + set_esep_pval(arg->buf32, j, arg->depth); + cc += x == 0xF; + } +#else + _foreach_h48sim(cube, arg->cocsepdata, arg->selfsim, 0, + j = coord_h48(cube, arg->cocsepdata, 0); + x = get_esep_pval(arg->buf32, j); + set_esep_pval(arg->buf32, j, arg->depth); + cc += x == 0xF; + ) +#endif + + break; } } diff --git a/test/111_gendata_h48_h0/00_h_0.in b/test/111_gendata_h48_h0/00_h_0.in deleted file mode 100644 index e69de29..0000000 diff --git a/test/111_gendata_h48_h0/00_h_0.out b/test/111_gendata_h48_h0/00_h_0.out deleted file mode 100644 index 04e8bf6..0000000 --- a/test/111_gendata_h48_h0/00_h_0.out +++ /dev/null @@ -1,23 +0,0 @@ -59903605 - -cocsepdata: -Classes: 3393 -Max value: 9 -0: 1 -1: 6 -2: 63 -3: 468 -4: 3068 -5: 15438 -6: 53814 -7: 71352 -8: 8784 -9: 96 - -h48: -0: 1 -1: 1 -2: 4 -3: 34 -4: 331 -5: 3612 diff --git a/test/111_gendata_h48_h0/gendata_h48_tests.c b/test/111_gendata_h48_h0/gendata_h48_tests.c deleted file mode 100644 index e9de3c0..0000000 --- a/test/111_gendata_h48_h0/gendata_h48_tests.c +++ /dev/null @@ -1,33 +0,0 @@ -#include "../test.h" - -#define MAXDEPTH 5 -#define COCSEPSIZE 1119792 -#define ETABLESIZE ((3393 * 495 * 70) >> 1) - -int64_t gendata_h48h0k4(void *, uint8_t); - -void run(void) { - char str[STRLENMAX]; - uint8_t i; - uint32_t *buf, *h48info; - size_t result; - - fgets(str, STRLENMAX, stdin); - buf = (uint32_t *)malloc(sizeof(uint32_t) * 60000000); - result = gendata_h48h0k4(buf, MAXDEPTH); - h48info = buf + (ETABLESIZE + COCSEPSIZE) / 4; - - printf("%zu\n\n", result); - - printf("cocsepdata:\n"); - printf("Classes: %" PRIu32 "\n", buf[COCSEPSIZE/4-12]); - printf("Max value: %" PRIu32 "\n", buf[COCSEPSIZE/4-11]); - for (i = 0; i < 10; i++) - printf("%" PRIu32 ": %" PRIu32 "\n", i, buf[COCSEPSIZE/4-10+i]); - - printf("\nh48:\n"); - for (i = 0; i < MAXDEPTH+1; i++) - printf("%" PRIu32 ": %" PRIu32 "\n", i, h48info[i+1]); - - free(buf); -} diff --git a/test/111_h48map/00_small.in b/test/111_h48map/00_small.in new file mode 100644 index 0000000..ee8e591 --- /dev/null +++ b/test/111_h48map/00_small.in @@ -0,0 +1,11 @@ +11 +7 +4 +34 +12 +45 +7 +34 +13 +45 +5 diff --git a/test/111_h48map/00_small.out b/test/111_h48map/00_small.out new file mode 100644 index 0000000..260e804 --- /dev/null +++ b/test/111_h48map/00_small.out @@ -0,0 +1,3 @@ +2 +34 12 +45 5 diff --git a/test/111_h48map/01_large.in b/test/111_h48map/01_large.in new file mode 100644 index 0000000..1812b40 --- /dev/null +++ b/test/111_h48map/01_large.in @@ -0,0 +1,303 @@ +307 +293 +150 +100053 +417 +100045 +164 +100007 +235 +100007 +207 +100011 +406 +100072 +29 +100033 +188 +100015 +358 +100013 +248 +100068 +218 +100047 +398 +100046 +263 +100000 +471 +100076 +219 +100021 +115 +100019 +329 +100015 +178 +100049 +59 +100052 +319 +100071 +232 +100058 +174 +100009 +46 +100060 +349 +100030 +287 +100051 +203 +100069 +359 +100011 +296 +100051 +223 +100014 +233 +100031 +264 +100017 +180 +100076 +22 +100016 +213 +100030 +55 +100037 +3 +100011 +467 +100002 +165 +100029 +161 +100022 +67 +100038 +374 +100075 +4 +100066 +156 +100051 +144 +100020 +480 +100039 +265 +100029 +195 +100087 +245 +100099 +287 +100041 +308 +100042 +32 +100026 +312 +100060 +434 +100006 +392 +100010 +269 +100079 +414 +100046 +161 +100086 +139 +100010 +88 +100036 +117 +100047 +376 +100069 +17 +100041 +314 +100074 +320 +100090 +225 +100092 +424 +100020 +325 +100096 +318 +100046 +238 +100028 +13 +100072 +73 +100096 +262 +100025 +82 +100001 +107 +100067 +410 +100044 +449 +100063 +276 +100026 +392 +100062 +407 +100091 +411 +100012 +400 +100073 +331 +100051 +83 +100010 +385 +100096 +484 +100043 +352 +100025 +207 +100077 +272 +100089 +192 +100005 +291 +100024 +243 +100091 +445 +100046 +162 +100053 +380 +100058 +157 +100065 +464 +100051 +306 +100056 +236 +100025 +198 +100093 +230 +100088 +494 +100033 +70 +100073 +218 +100048 +486 +100059 +77 +100027 +142 +100045 +418 +100012 +68 +100059 +448 +100084 +339 +100017 +39 +100048 +83 +100004 +321 +100051 +441 +100016 +308 +100088 +334 +100033 +476 +100064 +51 +100060 +324 +100043 +149 +100084 +116 +100026 +351 +100051 +396 +100060 +377 +100069 +301 +100015 +319 +100014 +466 +100038 +194 +100068 +41 +100038 +295 +100097 +394 +100017 +34 +100013 +223 +100053 +339 +100019 +67 +100018 +24 +100081 +205 +100071 +440 +100025 +228 +100014 +169 +100016 +121 +100011 +444 +100069 +460 +100079 +139 +100063 +169 +100070 +132 +100072 +119 +100095 +126 +100042 +217 +100008 +272 +100022 +121 diff --git a/test/111_h48map/01_large.out b/test/111_h48map/01_large.out new file mode 100644 index 0000000..f5e00d8 --- /dev/null +++ b/test/111_h48map/01_large.out @@ -0,0 +1,83 @@ +82 +100000 471 +100001 107 +100002 165 +100004 321 +100005 291 +100006 392 +100007 207 +100008 272 +100009 46 +100010 88 +100011 296 +100012 68 +100013 223 +100014 169 +100015 178 +100016 121 +100017 34 +100018 24 +100019 67 +100020 325 +100021 115 +100022 67 +100024 243 +100025 82 +100026 312 +100027 142 +100028 13 +100029 161 +100030 55 +100031 264 +100033 70 +100036 117 +100037 3 +100038 194 +100039 265 +100041 308 +100042 32 +100043 149 +100044 449 +100045 164 +100046 161 +100047 376 +100048 83 +100049 59 +100051 83 +100052 319 +100053 339 +100056 236 +100058 157 +100059 77 +100060 324 +100062 407 +100063 169 +100064 51 +100065 464 +100066 156 +100067 410 +100068 41 +100069 17 +100070 132 +100071 232 +100072 29 +100073 218 +100074 320 +100075 4 +100076 22 +100077 272 +100079 139 +100081 205 +100084 116 +100086 139 +100087 245 +100088 334 +100089 192 +100090 225 +100091 411 +100092 424 +100093 230 +100095 126 +100096 262 +100097 394 +100099 287 diff --git a/test/111_h48map/h48map_tests.c b/test/111_h48map/h48map_tests.c new file mode 100644 index 0000000..d70bc3a --- /dev/null +++ b/test/111_h48map/h48map_tests.c @@ -0,0 +1,83 @@ +#include "../test.h" + +#define MAP_KEYSHIFT UINT64_C(40) +#define MAXPOS 1000 + +typedef struct { + uint64_t n; + uint64_t capacity; + uint64_t randomizer; + uint64_t *table; +} h48map_t; + +typedef struct { + uint64_t key; + uint64_t val; +} kvpair_t; + +void h48map_create(h48map_t *, uint64_t, uint64_t); +void h48map_destroy(h48map_t *); +void h48map_insertmin(h48map_t *, uint64_t, uint64_t); +uint64_t h48map_value(h48map_t *, uint64_t); +kvpair_t h48map_nextkvpair(h48map_t *, uint64_t *); + +char str[STRLENMAX]; + +int compare(const void *x, const void *y) { + uint64_t a = ((kvpair_t *)x)->key; + uint64_t b = ((kvpair_t *)y)->key; + + if (a > b) return 1; + if (a == b) return 0; + return -1; +} + +uint64_t readl(void) { + fgets(str, STRLENMAX, stdin); + return atoll(str); +} + +void run(void) { + h48map_t map; + uint64_t n, i, j, capacity, randomizer, x, y, v; + kvpair_t kv, a[MAXPOS], b[MAXPOS]; + + capacity = readl(); + randomizer = readl(); + n = readl(); + + for (i = 0; i < n; i++) { + x = readl(); + y = readl(); + a[i] = (kvpair_t) { .key = x, .val = y }; + } + + h48map_create(&map, capacity, randomizer); + for (i = 0; i < n; i++) + h48map_insertmin(&map, a[i].key, a[i].val); + + i = 0; + for (kv = h48map_nextkvpair(&map, &i), j = 0; + i != map.capacity && j < MAXPOS; + kv = h48map_nextkvpair(&map, &i) + ) { + b[j++] = kv; + } + qsort(b, j, sizeof(kvpair_t), compare); + + printf("%" PRIu64 "\n", map.n); + for (i = 0; i < j; i++) + printf("%" PRIu64 " %" PRIu64 "\n", b[i].key, b[i].val); + if (map.n != j) + printf("Wrong number of elements: map->n = %" PRIu64 ", " + "but scan returns %" PRIu64 "\n", map.n, j); + for (i = 0; i < n; i++) { + v = h48map_value(&map, a[i].key); + if (v > a[i].val) + printf("Value for key %" PRId64 " is larger than " + "expected (%" PRIu64 " > %" PRIu64 ")\n", + a[i].key, v, a[i].val); + } + + h48map_destroy(&map); +} diff --git a/test/112_gendata_h48/00_h_0.in b/test/112_gendata_h48/00_h_0.in new file mode 100644 index 0000000..cb6e5ed --- /dev/null +++ b/test/112_gendata_h48/00_h_0.in @@ -0,0 +1,2 @@ +5 +0 diff --git a/test/112_gendata_h48/00_h_0.out b/test/112_gendata_h48/00_h_0.out new file mode 100644 index 0000000..04e8bf6 --- /dev/null +++ b/test/112_gendata_h48/00_h_0.out @@ -0,0 +1,23 @@ +59903605 + +cocsepdata: +Classes: 3393 +Max value: 9 +0: 1 +1: 6 +2: 63 +3: 468 +4: 3068 +5: 15438 +6: 53814 +7: 71352 +8: 8784 +9: 96 + +h48: +0: 1 +1: 1 +2: 4 +3: 34 +4: 331 +5: 3612 diff --git a/test/112_gendata_h48/gendata_h48_tests.c b/test/112_gendata_h48/gendata_h48_tests.c new file mode 100644 index 0000000..485d9d0 --- /dev/null +++ b/test/112_gendata_h48/gendata_h48_tests.c @@ -0,0 +1,43 @@ +#include "../test.h" + +#define COCSEPSIZE 1119792 +#define ETABLESIZE ((3393 * 495 * 70) >> 1) + +int64_t gendata_h48h0k4(void *, uint8_t); + +int64_t gendata_h48_fixture(void *buf, uint8_t maxdepth, uint8_t h) { + if (h == 0) + return gendata_h48h0k4(buf, maxdepth); + fprintf(stderr, "Error: gendata h48 for h>0 not implemented yet\n"); + exit(1); +} + +void run(void) { + char str[STRLENMAX]; + uint8_t i, maxdepth, h; + uint32_t *buf, *h48info; + size_t result; + + fgets(str, STRLENMAX, stdin); + maxdepth = atoi(str); + fgets(str, STRLENMAX, stdin); + h = atoi(str); + + buf = (uint32_t *)malloc(sizeof(uint32_t) * 60000000); + result = gendata_h48_fixture(buf, maxdepth, h); + h48info = buf + (ETABLESIZE + COCSEPSIZE) / 4; + + printf("%zu\n\n", result); + + printf("cocsepdata:\n"); + printf("Classes: %" PRIu32 "\n", buf[COCSEPSIZE/4-12]); + printf("Max value: %" PRIu32 "\n", buf[COCSEPSIZE/4-11]); + for (i = 0; i < 10; i++) + printf("%" PRIu32 ": %" PRIu32 "\n", i, buf[COCSEPSIZE/4-10+i]); + + printf("\nh48:\n"); + for (i = 0; i < maxdepth+1; i++) + printf("%" PRIu32 ": %" PRIu32 "\n", i, h48info[i+1]); + + free(buf); +} diff --git a/test/112_h48map/00_small.in b/test/112_h48map/00_small.in deleted file mode 100644 index ee8e591..0000000 --- a/test/112_h48map/00_small.in +++ /dev/null @@ -1,11 +0,0 @@ -11 -7 -4 -34 -12 -45 -7 -34 -13 -45 -5 diff --git a/test/112_h48map/00_small.out b/test/112_h48map/00_small.out deleted file mode 100644 index 260e804..0000000 --- a/test/112_h48map/00_small.out +++ /dev/null @@ -1,3 +0,0 @@ -2 -34 12 -45 5 diff --git a/test/112_h48map/01_large.in b/test/112_h48map/01_large.in deleted file mode 100644 index 1812b40..0000000 --- a/test/112_h48map/01_large.in +++ /dev/null @@ -1,303 +0,0 @@ -307 -293 -150 -100053 -417 -100045 -164 -100007 -235 -100007 -207 -100011 -406 -100072 -29 -100033 -188 -100015 -358 -100013 -248 -100068 -218 -100047 -398 -100046 -263 -100000 -471 -100076 -219 -100021 -115 -100019 -329 -100015 -178 -100049 -59 -100052 -319 -100071 -232 -100058 -174 -100009 -46 -100060 -349 -100030 -287 -100051 -203 -100069 -359 -100011 -296 -100051 -223 -100014 -233 -100031 -264 -100017 -180 -100076 -22 -100016 -213 -100030 -55 -100037 -3 -100011 -467 -100002 -165 -100029 -161 -100022 -67 -100038 -374 -100075 -4 -100066 -156 -100051 -144 -100020 -480 -100039 -265 -100029 -195 -100087 -245 -100099 -287 -100041 -308 -100042 -32 -100026 -312 -100060 -434 -100006 -392 -100010 -269 -100079 -414 -100046 -161 -100086 -139 -100010 -88 -100036 -117 -100047 -376 -100069 -17 -100041 -314 -100074 -320 -100090 -225 -100092 -424 -100020 -325 -100096 -318 -100046 -238 -100028 -13 -100072 -73 -100096 -262 -100025 -82 -100001 -107 -100067 -410 -100044 -449 -100063 -276 -100026 -392 -100062 -407 -100091 -411 -100012 -400 -100073 -331 -100051 -83 -100010 -385 -100096 -484 -100043 -352 -100025 -207 -100077 -272 -100089 -192 -100005 -291 -100024 -243 -100091 -445 -100046 -162 -100053 -380 -100058 -157 -100065 -464 -100051 -306 -100056 -236 -100025 -198 -100093 -230 -100088 -494 -100033 -70 -100073 -218 -100048 -486 -100059 -77 -100027 -142 -100045 -418 -100012 -68 -100059 -448 -100084 -339 -100017 -39 -100048 -83 -100004 -321 -100051 -441 -100016 -308 -100088 -334 -100033 -476 -100064 -51 -100060 -324 -100043 -149 -100084 -116 -100026 -351 -100051 -396 -100060 -377 -100069 -301 -100015 -319 -100014 -466 -100038 -194 -100068 -41 -100038 -295 -100097 -394 -100017 -34 -100013 -223 -100053 -339 -100019 -67 -100018 -24 -100081 -205 -100071 -440 -100025 -228 -100014 -169 -100016 -121 -100011 -444 -100069 -460 -100079 -139 -100063 -169 -100070 -132 -100072 -119 -100095 -126 -100042 -217 -100008 -272 -100022 -121 diff --git a/test/112_h48map/01_large.out b/test/112_h48map/01_large.out deleted file mode 100644 index f5e00d8..0000000 --- a/test/112_h48map/01_large.out +++ /dev/null @@ -1,83 +0,0 @@ -82 -100000 471 -100001 107 -100002 165 -100004 321 -100005 291 -100006 392 -100007 207 -100008 272 -100009 46 -100010 88 -100011 296 -100012 68 -100013 223 -100014 169 -100015 178 -100016 121 -100017 34 -100018 24 -100019 67 -100020 325 -100021 115 -100022 67 -100024 243 -100025 82 -100026 312 -100027 142 -100028 13 -100029 161 -100030 55 -100031 264 -100033 70 -100036 117 -100037 3 -100038 194 -100039 265 -100041 308 -100042 32 -100043 149 -100044 449 -100045 164 -100046 161 -100047 376 -100048 83 -100049 59 -100051 83 -100052 319 -100053 339 -100056 236 -100058 157 -100059 77 -100060 324 -100062 407 -100063 169 -100064 51 -100065 464 -100066 156 -100067 410 -100068 41 -100069 17 -100070 132 -100071 232 -100072 29 -100073 218 -100074 320 -100075 4 -100076 22 -100077 272 -100079 139 -100081 205 -100084 116 -100086 139 -100087 245 -100088 334 -100089 192 -100090 225 -100091 411 -100092 424 -100093 230 -100095 126 -100096 262 -100097 394 -100099 287 diff --git a/test/112_h48map/h48map_tests.c b/test/112_h48map/h48map_tests.c deleted file mode 100644 index d70bc3a..0000000 --- a/test/112_h48map/h48map_tests.c +++ /dev/null @@ -1,83 +0,0 @@ -#include "../test.h" - -#define MAP_KEYSHIFT UINT64_C(40) -#define MAXPOS 1000 - -typedef struct { - uint64_t n; - uint64_t capacity; - uint64_t randomizer; - uint64_t *table; -} h48map_t; - -typedef struct { - uint64_t key; - uint64_t val; -} kvpair_t; - -void h48map_create(h48map_t *, uint64_t, uint64_t); -void h48map_destroy(h48map_t *); -void h48map_insertmin(h48map_t *, uint64_t, uint64_t); -uint64_t h48map_value(h48map_t *, uint64_t); -kvpair_t h48map_nextkvpair(h48map_t *, uint64_t *); - -char str[STRLENMAX]; - -int compare(const void *x, const void *y) { - uint64_t a = ((kvpair_t *)x)->key; - uint64_t b = ((kvpair_t *)y)->key; - - if (a > b) return 1; - if (a == b) return 0; - return -1; -} - -uint64_t readl(void) { - fgets(str, STRLENMAX, stdin); - return atoll(str); -} - -void run(void) { - h48map_t map; - uint64_t n, i, j, capacity, randomizer, x, y, v; - kvpair_t kv, a[MAXPOS], b[MAXPOS]; - - capacity = readl(); - randomizer = readl(); - n = readl(); - - for (i = 0; i < n; i++) { - x = readl(); - y = readl(); - a[i] = (kvpair_t) { .key = x, .val = y }; - } - - h48map_create(&map, capacity, randomizer); - for (i = 0; i < n; i++) - h48map_insertmin(&map, a[i].key, a[i].val); - - i = 0; - for (kv = h48map_nextkvpair(&map, &i), j = 0; - i != map.capacity && j < MAXPOS; - kv = h48map_nextkvpair(&map, &i) - ) { - b[j++] = kv; - } - qsort(b, j, sizeof(kvpair_t), compare); - - printf("%" PRIu64 "\n", map.n); - for (i = 0; i < j; i++) - printf("%" PRIu64 " %" PRIu64 "\n", b[i].key, b[i].val); - if (map.n != j) - printf("Wrong number of elements: map->n = %" PRIu64 ", " - "but scan returns %" PRIu64 "\n", map.n, j); - for (i = 0; i < n; i++) { - v = h48map_value(&map, a[i].key); - if (v > a[i].val) - printf("Value for key %" PRId64 " is larger than " - "expected (%" PRIu64 " > %" PRIu64 ")\n", - a[i].key, v, a[i].val); - } - - h48map_destroy(&map); -} diff --git a/tools/01_gendata_h48/benchmark_gendata_h48.c b/tools/01_gendata_h48/benchmark_gendata_h48.c new file mode 100644 index 0000000..efb6f6f --- /dev/null +++ b/tools/01_gendata_h48/benchmark_gendata_h48.c @@ -0,0 +1,47 @@ +#include "../timerun.h" +#include "../../src/cube.h" + +#define MAXDEPTH 10 +#define HVALUE 2 +#define OPTIONS "2;10" +#define LONGOPTIONS "h = 2, max depth = 10" + +#define COCSEPSIZE 1119792 +#define ETABLESIZE(h) (((3393 * 495 * 70) >> 1) << (size_t)(h)) + +char *buf; + +void run(void) { + uint32_t *h48info; + int i; + int64_t s; + + s = nissy_gendata("H48", OPTIONS, buf); + + if (s == -1) { + printf("Error generating table\n"); + } else { + printf("Succesfully generated %" PRId64 " bytes. Table:\n", s); + h48info = (uint32_t *)buf + (ETABLESIZE(HVALUE) + COCSEPSIZE) / 4; + for (i = 0; i < MAXDEPTH+1; i++) + printf("%d:\t%" PRIu32 "\n", i, h48info[i+1]); + } +} + +int main() { + int64_t size; + + size = nissy_datasize("H48", OPTIONS); + if (size == -1) { + printf("gendata_h48 benchmark: error in datasize\n"); + return 1; + } + + buf = malloc(size); + + timerun(run, "benchmark gendata_h48 " LONGOPTIONS); + + free(buf); + + return 0; +} diff --git a/tools/02_stats_tables_h48/stats_tables_h48.c b/tools/02_stats_tables_h48/stats_tables_h48.c new file mode 100644 index 0000000..7c6bc3c --- /dev/null +++ b/tools/02_stats_tables_h48/stats_tables_h48.c @@ -0,0 +1,152 @@ +#include +#include +#include +#include "../timerun.h" +#include "../../src/cube.h" + +#define MAXMOVES 20 +#define NTHREADS 32 +#define NCUBES_PER_THREAD 10000 +#define LOG_EVERY (NCUBES_PER_THREAD / 10) + +typedef struct { + int n; + int thread_id; + int64_t v[12][100]; +} thread_arg_t; + +const char *filename = "tables/h48h0k4"; +char *buf; + +uint64_t rand64(void) { + uint64_t i, ret; + + for (i = 0, ret = 0; i < 64; i++) + ret |= (uint64_t)(rand() % 2) << i; + + return ret; +} + +void log_stderr(const char *str, ...) { + va_list args; + + va_start(args, str); + vfprintf(stderr, str, args); + va_end(args); +} + +static void * +run_thread(void *arg) +{ + char sols[12], cube[22]; + int64_t ep, eo, cp, co; + int i, j; + + thread_arg_t *a = (thread_arg_t *)arg; + + for (i = 0; i < a->n; i++) { + ep = rand64(); + eo = rand64(); + cp = rand64(); + co = rand64(); + nissy_getcube(ep, eo, cp, co, "fix", cube); + nissy_solve(cube, "h48stats", "", "", + 0, MAXMOVES, 1, -1, buf, sols); + for (j = 0; j < 12; j++) + a->v[j][(int)sols[j]]++; + if ((i+1) % LOG_EVERY == 0) + fprintf(stderr, "[thread %d] %d cubes solved...\n", + a->thread_id, i+1); + } + + return NULL; +} + +void run(void) { + int64_t i, j, k, tot; + double avg; + pthread_t thread[NTHREADS]; + thread_arg_t arg[NTHREADS]; + + for (i = 0; i < NTHREADS; i++) { + arg[i] = (thread_arg_t) { + .thread_id = i, + .n = NCUBES_PER_THREAD, + .v = {{0}} + }; + pthread_create(&thread[i], NULL, run_thread, &arg[i]); + } + + for (i = 0; i < NTHREADS; i++) + pthread_join(thread[i], NULL); + + for (j = 0; j < 12; j++) { + printf("Data for h=%" PRId64 "\n", j); + for (k = 0, avg = 0.0; k <= 16; k++) { + for (i = 0, tot = 0; i < NTHREADS; i++) + tot += arg[i].v[j][k]; + printf("%" PRId64 "\t%" PRId64 "\n", k, tot); + avg += tot * k; + } + avg /= (double)(NCUBES_PER_THREAD * NTHREADS); + printf("Average: %.4lf\n", avg); + printf("\n"); + } +} + +int getdata(int64_t size) { + int64_t s; + FILE *f; + + buf = malloc(size); + + if ((f = fopen(filename, "rb")) == NULL) { + fprintf(stderr, "Table file not found, generating them." + " This can take a while.\n"); + s = nissy_gendata("h48stats", "", buf); + if (s != size) { + fprintf(stderr, "Error generating table"); + if (s != -1) + fprintf(stderr, " (got %" PRId64 " bytes)", s); + fprintf(stderr, "\n"); + return 1; + } + if ((f = fopen(filename, "wb")) == NULL) { + fprintf(stderr, "Could not write tables to file %s" + ", will be regenerated next time.\n", filename); + } else { + fwrite(buf, size, 1, f); + fclose(f); + } + } else { + fprintf(stderr, "Reading tables from file %s\n", filename); + fread(buf, size, 1, f); + fclose(f); + } + + return 0; +} + +int main(void) { + int64_t size; + + srand(time(NULL)); + + nissy_setlogger(log_stderr); + size = nissy_datasize("h48stats", ""); + if (size == -1) { + printf("h48 stats: error in datasize\n"); + return 1; + } + + if (getdata(size) != 0) { + printf("Error getting table, stopping\n"); + free(buf); + return 1; + } + + timerun(run, "h48 table stats"); + + free(buf); + return 0; +} diff --git a/tools/benchmark_gendata_h48/benchmark_gendata_h48.c b/tools/benchmark_gendata_h48/benchmark_gendata_h48.c deleted file mode 100644 index efb6f6f..0000000 --- a/tools/benchmark_gendata_h48/benchmark_gendata_h48.c +++ /dev/null @@ -1,47 +0,0 @@ -#include "../timerun.h" -#include "../../src/cube.h" - -#define MAXDEPTH 10 -#define HVALUE 2 -#define OPTIONS "2;10" -#define LONGOPTIONS "h = 2, max depth = 10" - -#define COCSEPSIZE 1119792 -#define ETABLESIZE(h) (((3393 * 495 * 70) >> 1) << (size_t)(h)) - -char *buf; - -void run(void) { - uint32_t *h48info; - int i; - int64_t s; - - s = nissy_gendata("H48", OPTIONS, buf); - - if (s == -1) { - printf("Error generating table\n"); - } else { - printf("Succesfully generated %" PRId64 " bytes. Table:\n", s); - h48info = (uint32_t *)buf + (ETABLESIZE(HVALUE) + COCSEPSIZE) / 4; - for (i = 0; i < MAXDEPTH+1; i++) - printf("%d:\t%" PRIu32 "\n", i, h48info[i+1]); - } -} - -int main() { - int64_t size; - - size = nissy_datasize("H48", OPTIONS); - if (size == -1) { - printf("gendata_h48 benchmark: error in datasize\n"); - return 1; - } - - buf = malloc(size); - - timerun(run, "benchmark gendata_h48 " LONGOPTIONS); - - free(buf); - - return 0; -} diff --git a/tools/stats_tables_h48/stats_tables_h48.c b/tools/stats_tables_h48/stats_tables_h48.c deleted file mode 100644 index 7c6bc3c..0000000 --- a/tools/stats_tables_h48/stats_tables_h48.c +++ /dev/null @@ -1,152 +0,0 @@ -#include -#include -#include -#include "../timerun.h" -#include "../../src/cube.h" - -#define MAXMOVES 20 -#define NTHREADS 32 -#define NCUBES_PER_THREAD 10000 -#define LOG_EVERY (NCUBES_PER_THREAD / 10) - -typedef struct { - int n; - int thread_id; - int64_t v[12][100]; -} thread_arg_t; - -const char *filename = "tables/h48h0k4"; -char *buf; - -uint64_t rand64(void) { - uint64_t i, ret; - - for (i = 0, ret = 0; i < 64; i++) - ret |= (uint64_t)(rand() % 2) << i; - - return ret; -} - -void log_stderr(const char *str, ...) { - va_list args; - - va_start(args, str); - vfprintf(stderr, str, args); - va_end(args); -} - -static void * -run_thread(void *arg) -{ - char sols[12], cube[22]; - int64_t ep, eo, cp, co; - int i, j; - - thread_arg_t *a = (thread_arg_t *)arg; - - for (i = 0; i < a->n; i++) { - ep = rand64(); - eo = rand64(); - cp = rand64(); - co = rand64(); - nissy_getcube(ep, eo, cp, co, "fix", cube); - nissy_solve(cube, "h48stats", "", "", - 0, MAXMOVES, 1, -1, buf, sols); - for (j = 0; j < 12; j++) - a->v[j][(int)sols[j]]++; - if ((i+1) % LOG_EVERY == 0) - fprintf(stderr, "[thread %d] %d cubes solved...\n", - a->thread_id, i+1); - } - - return NULL; -} - -void run(void) { - int64_t i, j, k, tot; - double avg; - pthread_t thread[NTHREADS]; - thread_arg_t arg[NTHREADS]; - - for (i = 0; i < NTHREADS; i++) { - arg[i] = (thread_arg_t) { - .thread_id = i, - .n = NCUBES_PER_THREAD, - .v = {{0}} - }; - pthread_create(&thread[i], NULL, run_thread, &arg[i]); - } - - for (i = 0; i < NTHREADS; i++) - pthread_join(thread[i], NULL); - - for (j = 0; j < 12; j++) { - printf("Data for h=%" PRId64 "\n", j); - for (k = 0, avg = 0.0; k <= 16; k++) { - for (i = 0, tot = 0; i < NTHREADS; i++) - tot += arg[i].v[j][k]; - printf("%" PRId64 "\t%" PRId64 "\n", k, tot); - avg += tot * k; - } - avg /= (double)(NCUBES_PER_THREAD * NTHREADS); - printf("Average: %.4lf\n", avg); - printf("\n"); - } -} - -int getdata(int64_t size) { - int64_t s; - FILE *f; - - buf = malloc(size); - - if ((f = fopen(filename, "rb")) == NULL) { - fprintf(stderr, "Table file not found, generating them." - " This can take a while.\n"); - s = nissy_gendata("h48stats", "", buf); - if (s != size) { - fprintf(stderr, "Error generating table"); - if (s != -1) - fprintf(stderr, " (got %" PRId64 " bytes)", s); - fprintf(stderr, "\n"); - return 1; - } - if ((f = fopen(filename, "wb")) == NULL) { - fprintf(stderr, "Could not write tables to file %s" - ", will be regenerated next time.\n", filename); - } else { - fwrite(buf, size, 1, f); - fclose(f); - } - } else { - fprintf(stderr, "Reading tables from file %s\n", filename); - fread(buf, size, 1, f); - fclose(f); - } - - return 0; -} - -int main(void) { - int64_t size; - - srand(time(NULL)); - - nissy_setlogger(log_stderr); - size = nissy_datasize("h48stats", ""); - if (size == -1) { - printf("h48 stats: error in datasize\n"); - return 1; - } - - if (getdata(size) != 0) { - printf("Error getting table, stopping\n"); - free(buf); - return 1; - } - - timerun(run, "h48 table stats"); - - free(buf); - return 0; -} -- cgit v1.3