commit ada0084c4c1137d4e6f7f863fb66a8af77cf240d
parent ae1d9dd5a0d6ea1232b35d3001c88b7c67cc385a
Author: Robert Russell <robertrussell.72001@gmail.com>
Date: Sun, 24 Sep 2023 19:52:35 -0700
Document PAGE_LEN and LF_{NUM,DEN}
Diffstat:
2 files changed, 11 insertions(+), 13 deletions(-)
diff --git a/inc/table/impl/define.h b/inc/table/impl/define.h
@@ -7,18 +7,8 @@
* dict size n is always at least MAX(PROBE_LEN, PAGE_LEN). Actually, we also
* require the dict size to be at least R_CACHE_LINE_SIZE, so that the meta
* bytes occupy a whole number of cache lines, and so that pages are
- * cache-aligned in the common case of key types K and value types V such that
- * sizeof(K) * PAGE_LEN and sizeof(V) * PAGE_LEN are both multiples of
- * R_CACHE_LINE_SIZE. */
-
-/* PAGE_LEN should be a multiple of 8 for packing and alignment. */
-/* TODO: make these parameters programmer-controllable. PAGE_LEN == 8 is
- * a conservative choice. In most cases (i.e., with the key size being a
- * multiple of 8), PAGE_LEN == 1 causes no packing issues and would improve
- * caching performance with very large keys or values. */
-
-/* The dict size doubles when count + ntombs exceeds the proportion of the
- * dict size indicated by LF_NUM and LF_DEN. See exceeds_lf. */
+ * cache-aligned in the case where KSIZE * PAGE_LEN and VSIZE * PAGE_LEN
+ * are both multiples of R_CACHE_LINE_SIZE. */
/* TODO: At some point, we should replace SSE2 with AVX2... or should we?
* Longer probe vectors means higher chance of conflicts within one probe
diff --git a/inc/table/impl/macro.h b/inc/table/impl/macro.h
@@ -56,7 +56,12 @@
#define TABLE_METHOD(name) name
#endif
-// TODO: document page len and lf num/den
+/* PAGE_LEN_BITS should be chosen such that PAGE_LEN * KSIZE and
+ * PAGE_LEN * VSIZE are both divisible by alignof(K) and by alignof(V).
+ * The default basically guarantees this on 64 bit machines, but one might
+ * experience improved caching performance for large keys or values by
+ * decreasing PAGE_LEN (because lower PAGE_LEN causes corresponding keys and
+ * values to be closer in memory). See define.h for more details. */
#ifndef TABLE_PAGE_LEN_BITS
#define TABLE_PAGE_LEN_BITS 3u
@@ -64,6 +69,9 @@
#define TABLE_PAGE_LEN (1u << (TABLE_PAGE_LEN_BITS))
+/* The dict size doubles when count + ntombs exceeds the proportion of the
+ * dict size indicated by LF_NUM and LF_DEN. See exceeds_lf in define.h. */
+
#ifndef TABLE_LF_NUM
#define TABLE_LF_NUM 3u
#endif
