u/fanf2/radish.git
8 weeks agoREADME: markup fixes master
Tony Finch [Tue, 28 Jul 2020 01:11:01 +0000 (02:11 +0100)]
README: markup fixes

8 weeks agoREADME: fn is the most portable version
Tony Finch [Tue, 28 Jul 2020 01:07:43 +0000 (02:07 +0100)]
README: fn is the most portable version

8 weeks agoREADME: mention prefetching and DNS in the abstract
Tony Finch [Tue, 28 Jul 2020 01:04:38 +0000 (02:04 +0100)]
README: mention prefetching and DNS in the abstract

2 months agoLink to a twitter thread
Tony Finch [Mon, 20 Jul 2020 14:17:44 +0000 (15:17 +0100)]
Link to a twitter thread

2 months agoLink to my fork of NSD which uses my DNS-optimized qp-trie
Tony Finch [Mon, 20 Jul 2020 12:54:18 +0000 (13:54 +0100)]
Link to my fork of NSD which uses my DNS-optimized qp-trie

2 months agoDNS: an iterative Tnext()
Tony Finch [Wed, 8 Jul 2020 14:23:41 +0000 (15:23 +0100)]
DNS: an iterative Tnext()

Instead of recursively traversing the tree, walk down it while keeping
track of our target's immediate neighbours. The tree walk is very
similar to Tset(): we have to do a preliminary walk to find a
leaf (which will go off piste if our search key is not in the tree),
work out out the common prefix of the keys, then do a second walk with
the correct termination conditions.

2 months agoblog: note what computer I ran the benchmarks on
Tony Finch [Tue, 7 Jul 2020 19:27:01 +0000 (20:27 +0100)]
blog: note what computer I ran the benchmarks on

2 months agoREADME: link to new blog entry
Tony Finch [Mon, 6 Jul 2020 23:46:33 +0000 (00:46 +0100)]
README: link to new blog entry

2 months agoblog: the genesis of my DNS-trie
Tony Finch [Mon, 6 Jul 2020 23:42:49 +0000 (00:42 +0100)]
blog: the genesis of my DNS-trie

2 months agoREADME: good grief
Tony Finch [Sun, 5 Jul 2020 15:41:56 +0000 (16:41 +0100)]
README: good grief

2 months agoREADME: update another old link
Tony Finch [Sun, 5 Jul 2020 15:40:58 +0000 (16:40 +0100)]
README: update another old link

2 months agoREADME: fix links
Tony Finch [Sun, 5 Jul 2020 15:39:42 +0000 (16:39 +0100)]
README: fix links

2 months agoupdate README
Tony Finch [Sun, 5 Jul 2020 15:18:15 +0000 (16:18 +0100)]
update README

2 months agoDNS: hook it up to the build
Tony Finch [Sun, 5 Jul 2020 15:13:24 +0000 (16:13 +0100)]
DNS: hook it up to the build

2 months agoDNS: bodge for compatibility with other implementations
Tony Finch [Sun, 5 Jul 2020 14:43:41 +0000 (15:43 +0100)]
DNS: bodge for compatibility with other implementations

For testing and benchmark comparisons, tweak the name preparation so
that the DNS trie works like the other string trie implementations.

Fix the trie iteration code to call the name prep code so that it
isn't completely wrong....

2 months agoDNS: debug support for the test / benchmark harnesses
Tony Finch [Sun, 5 Jul 2020 13:41:50 +0000 (14:41 +0100)]
DNS: debug support for the test / benchmark harnesses

2 months agoDNS: an interim Tnextl()
Tony Finch [Sun, 5 Jul 2020 12:10:36 +0000 (13:10 +0100)]
DNS: an interim Tnextl()

This is basically the same as the existing ones so it's good enough to
get this working, but I think we should be able to do a lot better.

2 months agoDNS: preen
Tony Finch [Sun, 5 Jul 2020 10:46:51 +0000 (11:46 +0100)]
DNS: preen

2 months agoDNS: a better layout to support lexicographic ordering
Tony Finch [Sun, 5 Jul 2020 07:07:48 +0000 (08:07 +0100)]
DNS: a better layout to support lexicographic ordering

2 months agoInitial pass at a DNS trie
Tony Finch [Sun, 5 Jul 2020 04:12:24 +0000 (05:12 +0100)]
Initial pass at a DNS trie

2 months agonotes: preen terminology
Tony Finch [Sun, 5 Jul 2020 04:12:05 +0000 (05:12 +0100)]
notes: preen terminology

2 months agonotes: eager byte-to-bit is a better name for it
Tony Finch [Thu, 2 Jul 2020 19:37:34 +0000 (20:37 +0100)]
notes: eager byte-to-bit is a better name for it

2 months agonotes: preen
Tony Finch [Thu, 2 Jul 2020 19:31:34 +0000 (20:31 +0100)]
notes: preen

2 months agonotes: Mistakes Were Made
Tony Finch [Thu, 2 Jul 2020 19:22:43 +0000 (20:22 +0100)]
notes: Mistakes Were Made

2 months agonotes: more DNS thoughts
Tony Finch [Thu, 2 Jul 2020 18:53:46 +0000 (19:53 +0100)]
notes: more DNS thoughts

Combine May 2020's addenda with the notes from May 2017, and add some
thoughts on doing byte-to-bit conversion as part of name preparation.

3 months agoFix links to Knot DNS qp merge request.
Tony Finch [Mon, 1 Jun 2020 12:40:15 +0000 (13:40 +0100)]
Fix links to Knot DNS qp merge request.

Reported-by: Joseph Huang <josephshuang@gmail.com>
4 months agonotes: licence
Tony Finch [Fri, 1 May 2020 23:38:25 +0000 (00:38 +0100)]
notes: licence

4 months agoREADME: link to new notes
Tony Finch [Fri, 1 May 2020 23:34:49 +0000 (00:34 +0100)]
README: link to new notes

4 months agonotes: some more thoughts about DNS support
Tony Finch [Fri, 1 May 2020 23:25:29 +0000 (00:25 +0100)]
notes: some more thoughts about DNS support

17 months agobind9: update git repository address
Ondřej Herman [Thu, 25 Apr 2019 13:12:03 +0000 (15:12 +0200)]
bind9: update git repository address

2 years agoDo not try to compile broken WIP code
Tony Finch [Thu, 4 Jan 2018 18:34:25 +0000 (18:34 +0000)]
Do not try to compile broken WIP code

3 years agoRib compression for second search in Tset - probably wrong
Tony Finch [Fri, 2 Jun 2017 16:34:58 +0000 (17:34 +0100)]
Rib compression for second search in Tset - probably wrong

3 years agoRib compression for first search in Tset
Tony Finch [Fri, 2 Jun 2017 16:27:24 +0000 (17:27 +0100)]
Rib compression for first search in Tset

3 years agoRevert failed experiment
Tony Finch [Fri, 2 Jun 2017 16:15:59 +0000 (17:15 +0100)]
Revert failed experiment

3 years agoFailed experiment
Tony Finch [Fri, 2 Jun 2017 16:13:18 +0000 (17:13 +0100)]
Failed experiment

When inserting a new element, can we shortcut the search
for its location by scanning the twigs array for a leaf?
Turns out the answer is no, or at least not enough to
offset the cost of the scan.

3 years agoMake Tget and Tdel search loops more similar
Tony Finch [Fri, 2 Jun 2017 15:54:44 +0000 (16:54 +0100)]
Make Tget and Tdel search loops more similar

3 years agogeneric leaves: some caveats
Tony Finch [Sun, 28 May 2017 21:23:16 +0000 (22:23 +0100)]
generic leaves: some caveats

3 years agoConcatenate nodes when we can. Yowza.
Tony Finch [Sat, 27 May 2017 15:25:41 +0000 (16:25 +0100)]
Concatenate nodes when we can. Yowza.

3 years agoThe case where two trunks should be concatenated
Tony Finch [Sat, 27 May 2017 13:03:14 +0000 (14:03 +0100)]
The case where two trunks should be concatenated

3 years agoEven better
Tony Finch [Sat, 27 May 2017 12:56:27 +0000 (13:56 +0100)]
Even better

3 years agoMuch better clarity of thought about Tdel search loop
Tony Finch [Sat, 27 May 2017 12:42:28 +0000 (13:42 +0100)]
Much better clarity of thought about Tdel search loop

3 years agoCorrect return value!
Tony Finch [Fri, 26 May 2017 16:18:01 +0000 (17:18 +0100)]
Correct return value!

3 years agoTdel() done, with much head-scratching. Not sure if is is OK.
Tony Finch [Fri, 26 May 2017 16:16:20 +0000 (17:16 +0100)]
Tdel() done, with much head-scratching. Not sure if is is OK.

3 years agoAvoid NULL returns from realloc()
Tony Finch [Fri, 26 May 2017 15:11:20 +0000 (16:11 +0100)]
Avoid NULL returns from realloc()

Do the trim and insert in one go, so that the wrapper
function knows when it is safe to ignore a failure -
it is safe to keep using the old memory if we are
not gaining more than we are trimming.

3 years agoOther deletion cases. Moderately ugly.
Tony Finch [Fri, 26 May 2017 14:43:08 +0000 (15:43 +0100)]
Other deletion cases. Moderately ugly.

3 years agoReverse sense of hasconcat() to make trunkend()
Tony Finch [Fri, 26 May 2017 14:42:35 +0000 (15:42 +0100)]
Reverse sense of hasconcat() to make trunkend()

3 years agoDefinitely better
Tony Finch [Fri, 26 May 2017 13:58:59 +0000 (14:58 +0100)]
Definitely better

3 years agoYes, that's better
Tony Finch [Fri, 26 May 2017 13:56:52 +0000 (14:56 +0100)]
Yes, that's better

3 years agoUtility functions for inserting into and deleting from raw allocations
Tony Finch [Fri, 26 May 2017 13:51:48 +0000 (14:51 +0100)]
Utility functions for inserting into and deleting from raw allocations

3 years agoWIP working out how to delete from ribs
Tony Finch [Fri, 26 May 2017 13:09:07 +0000 (14:09 +0100)]
WIP working out how to delete from ribs

3 years agoA utility function to find out if there is a concatenated branch
Tony Finch [Fri, 26 May 2017 13:07:46 +0000 (14:07 +0100)]
A utility function to find out if there is a concatenated branch

3 years agoRe-jig the old twig deletion code to be more rib-friendly.
Tony Finch [Fri, 26 May 2017 12:34:27 +0000 (13:34 +0100)]
Re-jig the old twig deletion code to be more rib-friendly.

The old logic was based on the twig array index of the twig
to be deleted (called 's' in the code).

The rib compression code needs to delete a twig from the middle
of a heterogeneous allocation, which is easier to do knowing
the address and size of the allocation and the address and size
of the part to be deleted.

This lower-level view actually works pretty well in the old code,
since 't' (the pointer to the twig to be deleted) is equivalent to
's', so we can use it directly instead of re-calculating the
array index with another popcount.

3 years agorc: calculate the size of a trunk
Tony Finch [Fri, 26 May 2017 12:25:43 +0000 (13:25 +0100)]
rc: calculate the size of a trunk

3 years agoRename "next" field to "concat"
Tony Finch [Fri, 26 May 2017 12:04:44 +0000 (13:04 +0100)]
Rename "next" field to "concat"

Slightly more direct hint that the child branch is concatenated
onto the twig array of its parent.

3 years agoInitial Tget for rib compression
Tony Finch [Thu, 25 May 2017 16:34:43 +0000 (17:34 +0100)]
Initial Tget for rib compression

3 years agoSync up rc with fn - WIP
Tony Finch [Thu, 25 May 2017 16:15:15 +0000 (17:15 +0100)]
Sync up rc with fn - WIP

3 years agoNicer nibble extraction
Tony Finch [Thu, 25 May 2017 16:12:52 +0000 (17:12 +0100)]
Nicer nibble extraction

3 years agoFix build deps for fn
Tony Finch [Thu, 25 May 2017 16:10:55 +0000 (17:10 +0100)]
Fix build deps for fn

3 years agoNicer index word manipulation
Tony Finch [Thu, 25 May 2017 15:12:36 +0000 (16:12 +0100)]
Nicer index word manipulation

3 years agoLinks to fn variant from README
Tony Finch [Thu, 25 May 2017 14:48:20 +0000 (15:48 +0100)]
Links to fn variant from README

3 years agoRetain this version of 5-bit qp trie for reference
Tony Finch [Thu, 25 May 2017 14:45:11 +0000 (15:45 +0100)]
Retain this version of 5-bit qp trie for reference

3 years agoTry reverting prefetch changes for comparison
Tony Finch [Thu, 25 May 2017 14:26:58 +0000 (15:26 +0100)]
Try reverting prefetch changes for comparison

3 years agoUse the new benchmark script
Tony Finch [Thu, 25 May 2017 14:12:16 +0000 (15:12 +0100)]
Use the new benchmark script

3 years agoWhoops, that fix wasn't quite correct!
Tony Finch [Thu, 25 May 2017 14:08:38 +0000 (15:08 +0100)]
Whoops, that fix wasn't quite correct!

3 years agoFound the crash.
Tony Finch [Thu, 25 May 2017 13:56:51 +0000 (14:56 +0100)]
Found the crash.

I screwed up the tricky variable lifetimes in Tdelkv() by
overwriting the working copy of the parent's index word.
Simplify by explicitly recovering the index before deleting
the child.

3 years agoAvoid signed shift overflow here as well
Tony Finch [Thu, 25 May 2017 13:49:38 +0000 (14:49 +0100)]
Avoid signed shift overflow here as well

3 years agoAvoid signed shift overflow
Tony Finch [Thu, 25 May 2017 13:48:47 +0000 (14:48 +0100)]
Avoid signed shift overflow

3 years agoSomething's broken? this version works
Tony Finch [Thu, 25 May 2017 13:30:42 +0000 (14:30 +0100)]
Something's broken? this version works

3 years agoTry to improve prefetching
Tony Finch [Thu, 25 May 2017 13:11:16 +0000 (14:11 +0100)]
Try to improve prefetching

Prefetch the pointer (might be twigs or key) before looking at the
index, to discourage the compiler from delaying the prefetch.

3 years agoA cross between bench-multi and bench-more, with colours
Tony Finch [Thu, 25 May 2017 12:39:53 +0000 (13:39 +0100)]
A cross between bench-multi and bench-more, with colours

3 years agoPrint number of rounds when benchmarking
Tony Finch [Thu, 25 May 2017 12:38:45 +0000 (13:38 +0100)]
Print number of rounds when benchmarking

3 years agoFix benchmark compile failure when uint doesn't leak from system headers
Tony Finch [Thu, 25 May 2017 11:57:44 +0000 (12:57 +0100)]
Fix benchmark compile failure when uint doesn't leak from system headers

3 years agoClean more warnings in benchmark code
Tony Finch [Thu, 25 May 2017 11:30:33 +0000 (12:30 +0100)]
Clean more warnings in benchmark code

3 years agoClean warnings in benchmark code
Tony Finch [Thu, 25 May 2017 11:28:52 +0000 (12:28 +0100)]
Clean warnings in benchmark code

3 years agolooks like this debug sanity check really was bullshit
Tony Finch [Wed, 24 May 2017 22:47:15 +0000 (23:47 +0100)]
looks like this debug sanity check really was bullshit

3 years agoPropagate index word changes better
Tony Finch [Wed, 24 May 2017 22:44:57 +0000 (23:44 +0100)]
Propagate index word changes better

3 years agoMake debug mode run-time configurable
Tony Finch [Wed, 24 May 2017 22:43:55 +0000 (23:43 +0100)]
Make debug mode run-time configurable

3 years agorc should (in theory) be the same as fp. let's test it...
Tony Finch [Wed, 24 May 2017 15:23:03 +0000 (16:23 +0100)]
rc should (in theory) be the same as fp. let's test it...

3 years agorc-debug.c copied and refactored from fp-debug.c
Tony Finch [Wed, 24 May 2017 15:05:40 +0000 (16:05 +0100)]
rc-debug.c copied and refactored from fp-debug.c

3 years agorc: add Tnextl() refactored from fp.c
Tony Finch [Wed, 24 May 2017 14:48:34 +0000 (15:48 +0100)]
rc: add Tnextl() refactored from fp.c

3 years agorc: add Tsetl() refactored from fp.c
Tony Finch [Wed, 24 May 2017 14:35:49 +0000 (15:35 +0100)]
rc: add Tsetl() refactored from fp.c

3 years agoDecouple index word access from Trie / twig access.
Tony Finch [Wed, 24 May 2017 13:45:20 +0000 (14:45 +0100)]
Decouple index word access from Trie / twig access.

Once this mechanical refactoring is done, the rib compressed
layout will have bare index words between concatenated branches,
so the accessor functions need to handle bare index words.

This has turned out to be fairly clean so far, which is nice.

3 years agoSearching for an exact prefix match
Tony Finch [Wed, 24 May 2017 12:59:18 +0000 (13:59 +0100)]
Searching for an exact prefix match

3 years agoTweak bitstring title
Tony Finch [Wed, 24 May 2017 11:07:24 +0000 (12:07 +0100)]
Tweak bitstring title

3 years agoSome notes on bitstring keys and prefix matching
Tony Finch [Wed, 24 May 2017 11:06:14 +0000 (12:06 +0100)]
Some notes on bitstring keys and prefix matching

3 years agoMy old thoughts on embedding keys have been superseded
Tony Finch [Wed, 24 May 2017 11:02:59 +0000 (12:02 +0100)]
My old thoughts on embedding keys have been superseded

3 years agoAn opportunity for searches to fail earlier in double bitmap tries
Tony Finch [Wed, 24 May 2017 10:49:41 +0000 (11:49 +0100)]
An opportunity for searches to fail earlier in double bitmap tries

3 years agorc: reorder for slightly better exposition
Tony Finch [Tue, 23 May 2017 15:27:16 +0000 (16:27 +0100)]
rc: reorder for slightly better exposition

3 years agorc: add Tdelkv() refactored from fp.c
Tony Finch [Tue, 23 May 2017 15:16:34 +0000 (16:16 +0100)]
rc: add Tdelkv() refactored from fp.c

3 years agorc: add Tgetkv() refactored from fp.c
Tony Finch [Tue, 23 May 2017 14:33:39 +0000 (15:33 +0100)]
rc: add Tgetkv() refactored from fp.c

3 years agorc: suppress static_assert warnings
Tony Finch [Tue, 23 May 2017 14:29:50 +0000 (15:29 +0100)]
rc: suppress static_assert warnings

3 years agorc: static_assert for unenlightened compilers
Tony Finch [Tue, 23 May 2017 14:24:34 +0000 (15:24 +0100)]
rc: static_assert for unenlightened compilers

3 years agoStart implementing rib compression.
Tony Finch [Tue, 23 May 2017 14:05:20 +0000 (15:05 +0100)]
Start implementing rib compression.

So far this is just a refactoring of fp.h to make rc.h -
same functionality, but it should be implemented in a
more portable manner.

3 years agoPreen description of concatenated nodes with generic leaves
Tony Finch [Wed, 17 May 2017 14:02:06 +0000 (15:02 +0100)]
Preen description of concatenated nodes with generic leaves

3 years agoIndexing compactly stored DNS names
Tony Finch [Wed, 17 May 2017 14:00:34 +0000 (15:00 +0100)]
Indexing compactly stored DNS names

3 years agoMore notes on DNS names
Tony Finch [Wed, 17 May 2017 13:44:19 +0000 (14:44 +0100)]
More notes on DNS names

3 years agoDitch old DNS indexing method
Tony Finch [Wed, 17 May 2017 13:22:17 +0000 (14:22 +0100)]
Ditch old DNS indexing method

3 years agoBetter indexing method for DNS names
Tony Finch [Wed, 17 May 2017 13:15:11 +0000 (14:15 +0100)]
Better indexing method for DNS names

3 years agoNote double-bitmap branch layouts of various sizes
Tony Finch [Fri, 12 May 2017 11:28:12 +0000 (12:28 +0100)]
Note double-bitmap branch layouts of various sizes

3 years agoRedirect fix?
Tony Finch [Thu, 11 May 2017 11:50:02 +0000 (12:50 +0100)]
Redirect fix?