 andrew
|
c11b4714b5
|
Check more preconditions in Debug mode
|
2024-08-26 12:43:07 -07:00 |
|
|
andrew
|
bc13094406
|
Don't violate precondition in test_conflict_set.py
|
2024-08-26 11:13:16 -07:00 |
|
|
andrew
|
c9d742b696
|
Make explicit the precondition that versions must be <= latest version
|
2024-08-24 13:43:39 -07:00 |
|
|
andrew
|
795ae7cb01
|
Internal.h doesn't need to include <vector>
|
2024-08-24 10:38:07 -07:00 |
|
|
andrew
|
849e2d3e5c
|
Remove unused code
|
2024-08-22 22:31:36 -07:00 |
|
|
andrew
|
1560037680
|
Remove unused struct
|
2024-08-22 17:55:54 -07:00 |
|
|
andrew
|
764c31bbc8
|
Run skip list gc at 200% entry insertion rate
|
2024-08-22 17:26:08 -07:00 |
|
|
andrew
|
ee3361952a
|
Use better rng in skip list
low bits of lcg have low periods
|
2024-08-22 17:00:15 -07:00 |
|
|
andrew
|
8a04e57353
|
Add to corpus
|
2024-08-22 16:52:33 -07:00 |
|
|
andrew
|
7f86fdee66
|
Test 64 bit versions
Keep 32 bit versions the default though
|
2024-08-21 14:00:00 -07:00 |
|
|
andrew
|
442755d0a6
|
Update implementation notes
This doesn't really capture the complexity, but at least it's more
accurate
|
2024-08-21 14:00:00 -07:00 |
|
|
andrew
|
e15b3bb137
|
Bump version
|
2024-08-20 16:58:39 -07:00 |
|
|
andrew
|
311794c37e
|
Update GCOVR annotations now that jenkins agent has avx512
|
2024-08-20 16:34:27 -07:00 |
|
|
andrew
|
dfa178ba19
|
Add to corpus (from fuzzing on macos)
|
2024-08-20 13:32:04 -07:00 |
|
|
andrew
|
a16d18edfe
|
Update README.md
|
2024-08-20 12:03:27 -07:00 |
|
|
andrew
|
2b60287448
|
Partition valgrind into tests of size at most 100
|
2024-08-20 11:35:20 -07:00 |
|
|
andrew
|
0a9ac59676
|
Commit to non-simd Node3 implementations
|
2024-08-20 10:36:04 -07:00 |
|
|
andrew
|
e3a77ed773
|
Remove unnecessary casts
|
2024-08-20 10:30:27 -07:00 |
|
|
andrew
|
cdf9a8a7b0
|
Save 8 bytes in Node3
|
2024-08-20 10:30:07 -07:00 |
|
|
andrew
|
305dfdd52f
|
Change whitespace in node structs for consistency
|
2024-08-20 09:57:44 -07:00 |
|
|
andrew
|
7261c91492
|
Remove Node48::nextFree, and improve padding to save 8 bytes
|
2024-08-20 09:51:29 -07:00 |
|
|
andrew
|
f11720f5ae
|
Add to corpus
|
2024-08-19 21:52:47 -07:00 |
|
|
andrew
|
e2b7298af5
|
Instrument setOldestVersion for callgrind too
|
2024-08-19 21:32:04 -07:00 |
|
|
andrew
|
8e1e344f4b
|
Fix clang-18 warning about std::basic_string<uint8_t>
|
2024-08-17 16:40:32 -07:00 |
|
|
andrew
|
3634b6a59b
|
Simplify slightly in checkMaxBetweenExclusive
|
2024-08-17 14:34:13 -07:00 |
|
|
andrew
|
a3cc14c807
|
Fix double counting of remove node in showMemory mode
|
2024-08-17 13:43:47 -07:00 |
|
|
andrew
|
55b3275434
|
ifdef linux specific stuff
|
2024-08-16 16:23:46 -07:00 |
|
|
andrew
|
3a5b86ed9e
|
Ignore itlb in grafana instead
|
2024-08-16 16:02:01 -07:00 |
|
|
andrew
|
159f2eef74
|
Use group leader fd
Events in the same group should be associated with the same set of
instructions
|
2024-08-16 15:35:35 -07:00 |
|
|
andrew
|
2952abe811
|
Reorg headers and only print unexpected errno's
|
2024-08-16 14:25:41 -07:00 |
|
|
andrew
|
ce54746a4a
|
Add several new cache events to metrics
|
2024-08-16 12:48:22 -07:00 |
|
|
andrew
|
b15959d62c
|
Add more perf counters
|
2024-08-16 10:57:00 -07:00 |
|
|
andrew
|
b009de1c2b
|
Avoid branching on type twice in erase
|
2024-08-16 09:29:22 -07:00 |
|
|
andrew
|
55a230c75e
|
Remove dontInvalidate arg from erase
Use a new node member "endOfRange" instead
|
2024-08-16 09:08:56 -07:00 |
|
|
andrew
|
0711ec3831
|
Remove dead code
|
2024-08-15 20:19:00 -07:00 |
|
|
andrew
|
0280bd77e5
|
Skip "dontInvalidate" check in erase from gc
|
2024-08-15 19:07:53 -07:00 |
|
|
andrew
|
359f6f0042
|
Update README benchmarks
|
2024-08-15 18:53:42 -07:00 |
|
|
andrew
|
aa8504ddba
|
Add to corpus
|
2024-08-15 18:47:47 -07:00 |
|
|
andrew
|
fb7cf18f9b
|
Add some comments about safety of calling maxVersion
|
2024-08-15 17:35:55 -07:00 |
|
|
andrew
|
b808b97940
|
Remove a bunch of impl plumbing
By making it a precondition that nodes aren't the root for certain
functions
|
2024-08-15 17:15:37 -07:00 |
|
|
andrew
|
e480f66846
|
Have caller ensure root max version for insert
|
2024-08-15 17:05:10 -07:00 |
|
|
andrew
|
d5bc9221a0
|
Simplify addWriteRange slightly
|
2024-08-15 16:59:28 -07:00 |
|
|
andrew
|
9d23b81d6f
|
Bring in some of the changes from erase-between branch
|
2024-08-15 16:55:26 -07:00 |
|
|
andrew
|
0740dcad43
|
Strengthen checkMemoryBoundInvariants check for Node0
I think this is probably checked elsewhere, but let's check here too for
consistency
|
2024-08-14 14:28:28 -07:00 |
|
|
andrew
|
176df61321
|
Simplify handling of beginNode invalidation if begin is prefix of end
|
2024-08-14 14:26:13 -07:00 |
|
|
andrew
|
0a850f22e9
|
Update README benchmarks
|
2024-08-12 17:33:45 -07:00 |
|
|
andrew
|
479b39d055
|
Add to corpus
|
2024-08-12 17:28:19 -07:00 |
|
|
andrew
|
482408d725
|
Add GCOVR_EXCL_LINE to __builtin_unreachable
|
2024-08-12 17:07:55 -07:00 |
|
|
andrew
|
45995e3307
|
Update comments
|
2024-08-12 17:05:21 -07:00 |
|
|
andrew
|
359b0b29ff
|
Avoid function call if no partial key
|
2024-08-12 16:33:03 -07:00 |
|
|
andrew
|
54e47ebd40
|
Simplify insert loop
|
2024-08-12 16:25:12 -07:00 |
|
|
andrew
|
1c9dda68a6
|
Call consumePartialKey from getOrCreateChild
|
2024-08-12 16:24:05 -07:00 |
|
|
andrew
|
142455dd28
|
Move consumePartialKey, and allow empty partial key
|
2024-08-12 16:18:58 -07:00 |
|
|
andrew
|
567d385fbd
|
WIP create child in getOrCreateChild
|
2024-08-12 16:11:16 -07:00 |
|
|
andrew
|
8a44055533
|
Consume first byte in insert iteration
|
2024-08-12 15:39:09 -07:00 |
|
|
andrew
|
62516825d1
|
Try specifying filter multiple times
|
2024-08-12 15:26:36 -07:00 |
|
|
andrew
|
3d592bd6a9
|
Move longestCommonPrefix to its own file
|
2024-08-12 15:10:05 -07:00 |
|
|
andrew
|
f5f5fb620b
|
Run gc at 200%
150% pessimized the "real data" benchmark
|
2024-08-12 10:48:24 -07:00 |
|
|
andrew
|
e3d1b2e842
|
Add to corpus
After a bunch of fuzzing on "udon" (my new zen4 machine)
|
2024-08-09 19:48:22 -07:00 |
|
|
andrew
|
9f8800af16
|
Add more to corpus (from fuzzing on osx)
Maybe we should just accumulate the corpus instead of replacing it? That
should be easier on git right?
|
2024-08-09 18:06:54 -07:00 |
|
|
andrew
|
182c065c8e
|
Insert common prefix in addWriteRange
This allows us to use our optimized implementation for setting max
version along the search path instead of a one-off loop
|
2024-08-09 14:57:04 -07:00 |
|
|
andrew
|
2dba0d5be3
|
Have insert return a pointer to the in-tree pointer
|
2024-08-09 13:58:31 -07:00 |
|
|
andrew
|
a1dfdf355c
|
Use metrics to count change in entry count
This lets us run gc slower safely
|
2024-08-09 13:44:49 -07:00 |
|
|
andrew
|
15919cb1c4
|
Add range writes to server_bench
|
2024-08-09 13:43:24 -07:00 |
|
|
andrew
|
5ed9003a83
|
Bump version
|
2024-08-08 12:09:26 -07:00 |
|
|
andrew
|
84c6a2bfc2
|
Disable debug symbols and frame pointer for macos
This causes some versions of clang to crash
|
2024-08-08 11:51:13 -07:00 |
|
|
andrew
|
b5772a6aa0
|
Revert "Use homebrew clang for packaging for macos"
This reverts commit c20c08f112.
|
2024-08-08 11:50:13 -07:00 |
|
|
andrew
|
e6c39981b9
|
Bump version
|
2024-08-08 11:26:49 -07:00 |
|
|
andrew
|
c20c08f112
|
Use homebrew clang for packaging for macos
The default segfaults now for some reason
|
2024-08-08 11:06:26 -07:00 |
|
|
andrew
|
ac98d4a443
|
Remove always_inline attribute - it wasn't affecting codegen
|
2024-08-08 10:44:54 -07:00 |
|
|
andrew
|
1d9e8ab68b
|
Add missing test coverage for fixupMaxVersion for Node256
|
2024-08-07 17:02:19 -07:00 |
|
|
andrew
|
7d86beb14c
|
Revert 29c05187fb
We're already doing this in checkRangeStartsWith
|
2024-08-07 16:51:23 -07:00 |
|
|
andrew
|
2fa954ed36
|
Fix compiler warning
|
2024-08-07 16:25:49 -07:00 |
|
|
andrew
|
ded6e7fc2c
|
Require entry present for fixupMaxVersion
|
2024-08-06 17:59:38 -07:00 |
|
|
andrew
|
781ba15cae
|
Enforce that root does not have a partial key
|
2024-08-06 17:55:33 -07:00 |
|
|
andrew
|
9b56a74b2f
|
Update corpus
|
2024-08-06 17:43:48 -07:00 |
|
|
andrew
|
6da9cbdec9
|
Update benchmarks
|
2024-08-06 16:07:16 -07:00 |
|
|
andrew
|
29c05187fb
|
Early return if common prefix isn't a prefix of an entry
For range reads
|
2024-08-06 15:32:44 -07:00 |
|
|
andrew
|
d89028dd2f
|
Inline SearchStepWise into checkRangeRead
This improves clang codegen
|
2024-08-06 14:45:52 -07:00 |
|
|
andrew
|
09cf807747
|
Avoid some branches on node type while inserting
|
2024-08-06 13:51:49 -07:00 |
|
|
andrew
|
051eb5919d
|
Extract consumePartialKey to its own function
|
2024-08-06 13:20:44 -07:00 |
|
|
andrew
|
ed5589e4ed
|
Specialize partial key split for newly created Node3
|
2024-08-06 13:04:19 -07:00 |
|
|
andrew
|
a7b3d8fe4c
|
Clarify insert documentation
|
2024-08-06 11:29:33 -07:00 |
|
|
andrew
|
c3a047fdf8
|
Handle newly-created node partial key immediately
|
2024-08-06 09:22:21 -07:00 |
|
|
andrew
|
b4b469a175
|
Use maxOfMax in fixupMaxVersion
|
2024-08-05 21:41:49 -07:00 |
|
|
andrew
|
0201e27498
|
Remove redundant setMaxVersion calls
|
2024-08-05 19:29:38 -07:00 |
|
|
andrew
|
2010920a2c
|
Correct comment
|
2024-08-05 19:28:24 -07:00 |
|
|
andrew
|
19af8da65c
|
Fix endNode's max version after the fact
This sets us up to unconditionally update the max version along the
search path for inserts, and avoid dispatching on type twice per
iteration.
|
2024-08-05 17:50:26 -07:00 |
|
|
andrew
|
80785e3c3b
|
Avoid switch on parent type for max version during search
|
2024-08-05 16:40:58 -07:00 |
|
|
andrew
|
4580ee44b4
|
Add range reads to ServerBench
|
2024-08-05 15:44:13 -07:00 |
|
|
andrew
|
2d3985ca40
|
Add a simple point read/write workload to ServerBench
|
2024-08-05 14:37:00 -07:00 |
|
|
andrew
|
c8be68db40
|
Add ServerBench.cpp
|
2024-08-05 12:20:38 -07:00 |
|
|
andrew
|
f5d021d6b6
|
Add multi-version rezero16
|
2024-08-03 14:22:50 -07:00 |
|
|
andrew
|
1c41605b53
|
Use std::countr_zero instead of __builtin_ctz
Doesn't seem to affect codegen in these cases.
|
2024-08-03 10:01:12 -07:00 |
|
|
andrew
|
8f03a105bb
|
Use target avx512f,avx512bw
Appears to fix gcc build
|
2024-08-02 21:47:23 -07:00 |
|
|
andrew
|
0e574856be
|
Make checkMaxBetweenExclusive a multi-version function
This introduces more branches but reduces code size
|
2024-08-02 21:09:55 -07:00 |
|
|
andrew
|
493a6572ad
|
Only exclude avx512-targeted functions from coverage
|
2024-08-02 20:53:30 -07:00 |
|
|
andrew
|
abce4591d0
|
Fix preprocessor guard for avx512 longestCommonPrefix
|
2024-08-02 20:46:32 -07:00 |
|
|
andrew
|
d1dc1247e1
|
Switch to new machine for benchmarks
|
2024-08-02 18:18:36 -07:00 |
|
|
andrew
|
f1ad68109a
|
Skip lcp call in SearchStepWise if no partial key
|
2024-08-02 18:16:55 -07:00 |
|