Making generalized Trie type in D

[Roman D. Boiko]

On Monday, 4 June 2012 at 19:18:32 UTC, Dmitry Olshansky wrote:
> On 04.06.2012 22:42, Roman D. Boiko wrote:
>> ... it is possible to create persistent (immutable) tries
>> with efficient (log N) inserting / deleting (this scenario is 
>> very important for my DCT project). Immutable hash tables 
>> would require 0(N) copying for each insert / delete.
>
> Aye, the good thing about them - the amount of data affected by 
> any change is localized to one "page". So you just copy it over 
> and remap indices/pointers.
Actually, Microsoft went this way (immutable hash tables) in 
their Roslyn preview implementation. However, I still believe 
that tries will work better here. Will check...

Would bulk pre-allocation of memory to be used by trie improve 
locality? With some heuristics for copying when it goes out of 
control.

>> It is difficult to create a good API for fundamental data 
>> structures,
>> because various use cases would motivate different trade-offs. 
>> The same
>> is true for implementation. This is why I like your decision to
>> introduce policies for configuration. Rationale and use cases 
>> should
>> help to analyze design of your API and implementation, thus 
>> you will get
>> better community feedback :)
>
> Well I guess I'll talk in depth about them in the article, as 
> the material exceed sane limits of a single NG post.
>
> In brief:
> 	- multiple levels are stored in one memory chunk one after 
> another thus helping a bit with cache-locality (first level 
> goes first)
> 	- constructors do minimize number of "pages" on each level by 
> constructing it outwards from the last level and checking 
> duplicates (costs ~ O(N^2) though, IRC)
So this price is paid only on construction, right? Are there 
alternatives to chose from (when needed)? If yes, which?

> 	- I learned the hard way not to introduce extra conditionals 
> anywhere, so there is no "out of range, max index, not 
> existent" crap, in all cases it's clean-cut memory access. 
> Extra bits lost on having at least one "default" page per level 
> can be saved by going extra level
Could you please elaborate? How do you handle situations when not 
existent, etc., is needed?

>> Your examples deal with lookup by the whole word (first/last 
>> characters and length are needed). Are your API and 
>> implementation adaptable for character-by-character trie 
>> lookup?
>
> I would say that one by one won't help you much since the speed 
> is almost the same if not worse.
I guess, in general your statement is true, especially because 
known length could improve speed significantly. Not sure (but can 
easily believe) that in my particular situation it is true. For 
example, one by one would allow ignoring key encoding (and thus 
using multiple encodings simultaneously just as easily as single).

> The problematic thing with one by one - say you want to stop 
> early, right?
Why? I'd like to lex inout as TokenKind.InOut, not TokenKind.In 
followed by TokenKind.Out. Did I misunderstand your question?

> Now you have to check the *NOT FOUND* case, and that implies 
> extra branching (if(...)) on _each level_ and maybe reusing 
> certain valid values as "not found" marker (extra 
> configuration?).
This should be easy, if something is not a keyword, it is likely 
an identifier. But I agree in general, and probably even in my 
case.

> Branching and testing are things that kill speed advantage of 
> Tries, the ones I overlooked in my previous attempt, see 
> std/internal/uni.d.
> The other being separate locations for data and index, 
> pointer-happy disjoint node(page) locality is another way of 
> the same fault.
This concern disturbs me for some time already, and slightly 
demotivates, because implementing something this way will likely 
lead to a failure. I don't have enough experience with 
alternatives to know their advantages and trade-offs. I'll check 
your code. I did plan to try table lookup instead of branching. I 
guess making my own mistakes is necessary anyway.

>> Will compile-time generation of lookup code based on tries be 
>> supported?
>> Example which is currently in DCT (first implemented by Brian 
>> Schott in
>> his Dscanner project) uses switch statements (which means 
>> lookup linear
>> in number of possible characters at each position).
>
> Nope, the days of linear lookup for switch are over (were there 
> even such days?) compiler always do binary search nowadays if 
> linear isn't more efficient e.g. for a small number of 
> values.(it even weight out which is better and uses a 
> combination of them)
I thought this *might* be the case, but didn't know nor checked 
anywhere. I also wanted to do linear search for some empirically 
chosen small number of items.

> However you'd better check asm code afterwards. Compiler is 
> like a nasty stepchild it will give up on generating good old 
> jump tables given any reason it finds justifiable. (but it may 
> use few small jump tables + binary search, could be fine... if 
> not in a tight loop!)
Thanks.

>> A trivial
>> improvement might be using if statements and binary lookup. 
>> (E.g., if
>> there are 26 possible characters used at some position, use 
>> only 5
>> comparisons, not 26).
>>
>
> Moreover you'd be surprised but such leap-frog binary search 
> looses by a big margin to _multilayer_ lookup table. (I for one 
> was quite shocked back then)
Thanks again :) Are any numbers or perf. tests available?

>> I wanted to analyse your regex implementation, but that's not 
>> an easy
>> task and requires a lot of effort...
>
> Yeah, sorry for some encrypted Klingon here and there ;)
>
>>It looks like the most promising
>> alternative to binary trie lookup which I described in previous
>> paragraph. Similarities and differences with your regex design 
>> might
>> also help us understand tries better.
>
> Well if you are in no rush you might as well just take my 
> latest development in the ways of Trie from my gsoc fork :)
> Skipping some gory days of try and trial (fail) in the process 
> ;)
OK