weaselbot/conflict-set
1
Fork 0
forked from weaselab/conflict-set
Code Pull Requests Activity
777 Commits 8 Branches 13 Tags
erase-between
Commit Graph
505 Commits
Author SHA1 Message Date
andrew 648b0b9238 Add an always_inline, with explanatory comment 2024-06-28 19:55:33 -07:00
andrew d3f4afa167 More SIMD for scanning Node256 with 32-bit versions 2024-06-28 19:48:06 -07:00
andrew f762add4d6 Write vectorized 32-bit compare by hand for arm in scan16 2024-06-28 17:28:59 -07:00
andrew b311e5f1f0 Add an experimental, disabled 32 bit internal version 
I think it's only missing detection for full-precision versions more
than 2e9 apart
 2024-06-28 15:53:35 -07:00
andrew ff81890921 Rename MaxVersionT to InternalVersionT 2024-06-28 14:34:48 -07:00
andrew 0e96177f5c Allow to easily experiment with 32 bit "max version" type 2024-06-28 13:54:12 -07:00
andrew efb0e52a0a SIMD implementation of scan16 for x86 
Closes #29
 2024-06-27 22:21:41 -07:00
andrew 2df7000090 Remove switch on phase from Stepwise left/right step 2024-06-27 20:51:35 -07:00
andrew 5378a06c39 Vectorize all bounds checks for Node256 scan 2024-06-27 17:40:23 -07:00
andrew 12c6ed2568 Reorganize to prepare for better vectorized first/last page 2024-06-27 17:21:41 -07:00
andrew c065b185ae Vectorize inner page check for Node256 2024-06-27 17:09:45 -07:00
andrew 639518bed4 Share "scan16" between Node16 and Node48 2024-06-27 13:22:51 -07:00
andrew 7de983cc15 Simd bounds checking for scan for Node16 2024-06-27 13:08:12 -07:00
andrew 1b4b61ddc6 Write Node16 scan in a "more vectorized" style 2024-06-27 12:07:38 -07:00
andrew bff7b85de2 Remove "Child" struct 2024-06-27 10:03:14 -07:00
andrew 9108ee209a SoA instead of AoS for child, maxVersion 2024-06-27 09:57:54 -07:00
andrew f8bf1c6eb4 Remove unreachable code 2024-06-26 22:14:27 -07:00
andrew 4da2a01614 Use single &, to show branch-free intent 2024-06-26 22:14:05 -07:00
andrew bb0e654040 Fix missed update for Node48::maxOfMax 2024-06-26 22:11:33 -07:00
andrew 02866a8cae Save some bounds checking for scanning Node256 2024-06-26 20:55:18 -07:00
andrew fa86d3e707 "max of max" for Node48 again, but physical instead of logical 2024-06-26 20:41:27 -07:00
andrew 7d1d1d7b2a Maintain childMaxVersion == 0 for unused children in Node48 2024-06-26 20:16:50 -07:00
andrew 789ecc29b3 Use unsigned compare trick to check in bounds 2024-06-26 19:41:25 -07:00
andrew 08f2998a85 Use 8 byte pages for "max of max" 
This seems to benchmark better
 2024-06-26 19:18:38 -07:00
andrew c882d7663d Maintain "reverseIndex" in Node48 2024-06-26 19:11:34 -07:00
andrew bfea4384ba Branchless inner page check for Node256 2024-06-26 18:28:41 -07:00
andrew 6520e3d734 "max of max" for Node48 2024-06-26 17:54:03 -07:00
andrew 22e4ab01a1 Track "max of max" versions in Node256 2024-06-26 16:28:24 -07:00
andrew b3aeed0caa Warning: interface change! Require versions >= 0 2024-06-26 15:46:36 -07:00
andrew 5f3833e965 Change maxVersion to return by value, and add setMaxVersion 2024-06-26 15:33:15 -07:00
andrew 8b1cd9c052 Minor improvements to checkMaxBetweenExclusive 2024-06-26 15:06:50 -07:00
andrew 488c723726 Improve worst-case radix tree checkRangeRead 2024-06-25 21:22:55 -07:00
andrew 2eb461b8ea Fix build for llvm 18 2024-06-11 11:38:55 -07:00
andrew 6e63fd5126 Add internal entry points, with test coverage 
Closes #25
 2024-04-19 11:23:25 -07:00
andrew d2e1863593 Account for every uncovered line in the implementation 
Closes #23
 2024-04-18 12:43:48 -07:00
andrew c15d296432 Exercise copyChildrenAndKeyFrom for Node{48,256} to itself 2024-04-17 17:13:22 -07:00
andrew 309d315956 Add DebugConflictSet, which asserts using skip list as a reference 
CC #23
 2024-04-17 12:08:39 -07:00
andrew 85db1a8786 Allow to choose implementation in python wrapper 
And fix a few minor bugs to make the python tests pass for skip_list.

CC #23
 2024-04-17 12:08:28 -07:00
andrew fd93300ce8 Tweaks and add more planned sections 2024-04-16 17:36:29 -07:00
andrew ad91fb36a5 Symbol tests for macos + whitelist imports/exports 
commit 1ad8276100
Author: Andrew Noyes <andrew@weaselab.dev>
Date:   Wed Apr 3 12:44:35 2024 -0700

    Add symbols for arm build

commit 058e4d5302
Author: Andrew Noyes <andrew@weaselab.dev>
Date:   Wed Apr 3 12:42:48 2024 -0700

    Add _GLOBAL_OFFSET_TABLE_

commit a201f3ada8
Author: Andrew Noyes <andrew@weaselab.dev>
Date:   Wed Apr 3 12:34:05 2024 -0700

    Add memset to symbol imports

commit c1129ed0e2
Author: Andrew Noyes <andrew@weaselab.dev>
Date:   Wed Apr 3 12:32:28 2024 -0700

    Add symbol imports file

commit 618766ce2e
Author: Andrew Noyes <andrew@weaselab.dev>
Date:   Wed Apr 3 12:27:07 2024 -0700

    Fix objcopy filepath

commit e774a90007
Author: Andrew Noyes <andrew@weaselab.dev>
Date:   Wed Apr 3 12:24:44 2024 -0700

    Use shellcheck precommit without docker

commit baddea7f57
Author: Andrew Noyes <andrew@weaselab.dev>
Date:   Wed Apr 3 12:20:26 2024 -0700

    Update and freeze pre-commit hooks

commit 2d3e7b9004
Author: Andrew Noyes <andrew@weaselab.dev>
Date:   Wed Apr 3 12:19:55 2024 -0700

    Add shellcheck to pre-commit

    Closes #22

commit c4862fee9b
Author: Andrew Noyes <andrew@weaselab.dev>
Date:   Wed Apr 3 12:15:08 2024 -0700

    Add symbol tests for apple

    closes #21
 2024-04-03 12:50:51 -07:00
andrew ab211c646a Apply compiler-appeasing syntax changes from Taoxi 2024-03-28 14:57:31 -07:00
andrew 0a1843a161 Add USE_SIMD_FALLBACK 2024-03-28 11:12:50 -07:00
andrew 4edf0315d9 Find insertion point for Node16 with simd 
Closes #13
 2024-03-28 10:47:20 -07:00
andrew 5cf43d1bfa Add weaselab namespace 2024-03-27 16:07:05 -07:00
andrew c15c2e7b44 Remove redundant static assert 
Closes #14
 2024-03-27 12:41:45 -07:00
andrew b7cdecaf71 Document thread-safety in terms of constness 2024-03-20 16:16:15 -07:00
andrew cda28643a6 Fix ConflictSet_getBytes 2024-03-20 16:15:43 -07:00
andrew 6222b74787 Fix tests 
Add the new symbol, and update the valgrind client request so that
Node::partialKeyCapacity is defined.
 2024-03-20 12:21:59 -07:00
andrew 19edc6f78f Interface change! Add ConflictSet::getBytes 
Closes #12
 2024-03-20 12:11:34 -07:00
andrew becfd25139 De-templatize kUseFreeList 
This results in smaller code. This is part of the "let the compiler be
in charge of inlining decisions" theme.
 2024-03-19 15:12:31 -07:00