andrew
72469ebb6e
Erase along left spine. Not faster
2024-08-15 15:07:44 -07:00
andrew
405a2ca161
Fix typo
2024-08-15 13:52:51 -07:00
andrew
f93466316a
Pass in-tree reference to mergeWithChild
2024-08-15 13:52:06 -07:00
andrew
41840220c3
Optimize version handling in mergeWithChild
2024-08-15 11:49:13 -07:00
andrew
7ff00e7846
Extract mergeWithChild to function
2024-08-15 11:40:52 -07:00
andrew
6242f40d48
Require that eraseBetween leave at least one child or entryPresent
2024-08-15 11:37:36 -07:00
andrew
403d70a1d3
Prefer not copying node in eraseBetween
...
If numChildren + entryPresent is enough, we don't have to copy even if
it would fit in a smaller node.
If we have to copy, we might as well use the smallest acceptable node
type.
2024-08-15 11:33:16 -07:00
andrew
9763452713
Separate beginIsPrefix path and simplify slightly
2024-08-15 11:29:15 -07:00
andrew
73d0593fca
Remove separate prefix write codepath for now
2024-08-14 21:29:43 -07:00
andrew
23c2a3e1c6
SIMD for eraseBetween (Node16)
2024-08-14 18:12:46 -07:00
andrew
a64e792964
Remove unused function
2024-08-14 17:40:04 -07:00
andrew
cc526cb6ba
Call eraseBetween on useAsRoot in addWriteRange
2024-08-14 17:08:55 -07:00
andrew
7e49888bec
More eraseBetween optimizations
2024-08-14 16:40:29 -07:00
andrew
e64ebabced
eraseBetween optimizations
2024-08-14 16:13:37 -07:00
andrew
1e34951a77
Fix use-of-uninit in eraseBetween (Node256)
2024-08-14 15:25:10 -07:00
andrew
baf64520d6
Have eraseBetween take in-tree node by reference
2024-08-14 15:04:11 -07:00
andrew
3499626127
Fix potential strict aliasing issues
2024-08-14 15:01:34 -07:00
andrew
b7f9084694
destroyTree -> eraseTree. Use freelist
2024-08-14 14:47:22 -07:00
andrew
4b82502946
Accept node by ref for eraseBetween again
2024-08-14 14:43:19 -07:00
andrew
68bbacb69a
Use getInTree in eraseBetween
2024-08-14 14:43:19 -07:00
andrew
3078845673
Fix nodes_released accounting
2024-08-14 14:43:19 -07:00
andrew
43f6126cc4
Add a missing assert, call to removeNode
2024-08-14 14:43:19 -07:00
andrew
b911d87d55
eraseBetween bug fixes
2024-08-14 14:43:19 -07:00
andrew
0c65a82b78
Separate codepath for prefix writes
...
Uses the newly-added eraseBetween
2024-08-14 14:43:19 -07:00
andrew
e024cb8291
Track entriesErased in destroyTree
2024-08-14 14:43:19 -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
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
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
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
ac98d4a443
Remove always_inline attribute - it wasn't affecting codegen
2024-08-08 10:44:54 -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
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