Cross-posting from my GSOC list as I think we had a lack of D rox posts lately :)

I rarely am surprised by generic code flexibility and power these days.
But once I fleshed out last bits of generalized Trie I was amazed.

In short: it allows something like "make a multistage integer lookup table using these x upper bits, these y bits in the middle and those last z bits as final offset" as one-liner. Better yet strings and other keys are just as easy, and even better it's up to user to allow custom ways of getting X bits for any key.
And while I writing this bit-packing is on it's way to get integrated thus obtaining ultra-small tables (we can pack even index entries since we know how much bits they take exactly).

And last but no least - it's easy to strap Trie on top of some other container (say arrays, sets, hashtable etc.).  (currently it doesn't play nice with GC-ed objects, I'll fix it later)
Say book catalog that goes by first latter (or two) as Trie stage then as final slot uses sorted array. The advantages  of such schemes is that re-sorting huge arrays  can get costly, moreover insertion can reallocate and that might even run out of memory while duping it. On the other hand smaller array keep sorting bounded at acceptable level.

(In fact hashtable is a degenerate case of 1-level Trie on top of e.g. List, just not space-optimized and with a weird  index transform).

To give you a taste of this power, consider a simple example - keyword recognizer. I'm showing two version first just checks if it's a keyword. Second one does catalogs it to specific kind.
(sample material taken from DCT project, thanks goes to Roman Boiko)

enum keywords = [
            "abstract",
            "alias",
            "align",
            //...  all of them, except @ ones
            "__traits"
    ];

//here is bare minumum set type usable for Trie
 struct SmallMap(size_t N, V, K)
    {
        void insert(Tuple!(V, K) t){ _set.insert(t); }

        V opBinaryRight(string op, T)(T key)
            if(op == "in")
        {
            auto idx = map!"a[1]"(_set.items[]).countUntil(key);
            return idx < 0 ? V.init : _set.items[idx][0];
        }
        private:
            SmallSet!(N, Tuple!(V, K)) _set;
    }
//define how we get bits for our index
   size_t useLength(T)(T[] arr)
    {
        return arr.length > 63 ? 0 : arr.length; //need max length, 64 - 6bits
    }

    template useLastItem(T)
    {
        size_t entity(in T[] arr){ return arr[$-1]; }
        enum bitSize = 8*T.sizeof;
    }
    //... useItemAt is similar


//now the usage:
auto keyTrie = Trie!(SetAsSlot!(SmallSet!(2,string))
                         , string
                         , assumeSize!(6, useLength)
                         , useItemAt!(0, char)
                         , useLastItem!(char)
                        )(keywords);

foreach(key; keywords)
//opIndex gives us a slot, here slot is set so test it with 'in'
        assert( key in keyTrie[key]);


And that's it. Importantly there is not a single bit of hardcoding here:
    - we choose to make Trie of sets by passing SetAsSlot for value type (simple Trie may just use say bool)
    - key type is string oviously
    - assumeSize takes a user define functor and "trusts" user that it is result indeed fits into X bit wide integer
    - the the table as constructed goes by levels: by length -> by first char -> by last char -> <small set>

As you can observe "alias" and "align" do collide after 3 levels passed, thus we go for fixed 2-slot sets at the end to resolve it and a few others.
Of course there are better ways to handle level that would prevent this "collision" and reduce size, it's just to show how Trie on top of Set works. (not to mention all keywords are ASCII alphas, hinting on better compression in say 6bits)

And here is how it can work with Maps as slot (the above was mapping to booleans in fact):

auto keywordsMap = [
            "abstract" : TokenKind.Abstract,
            "alias" : TokenKind.Alias,
            "align" : TokenKind.Align,
            //... all others, cataloged per their kind
            "__thread" : TokenKind._Thread,
            "__traits" : TokenKind._Traits,
    ];

//now the usage:
auto keyTrie = Trie!(SetAsMap!(SmallMap!(2, TokenKind, string), TokenKind, string)
//duplication is because not every Map type Key-Value can be derived (we have no standard protocol for AAs)
                         , string
                         , assumeSize!(6, useLength)
                         , useItemAt!(0, char)
                         , useLastItem!(char)
                        )(keywordsMap);

 foreach(k,v; keywordsMap)
        assert((k in keyTrie2[k]) == v);

And the only big change is the data type :

struct SmallMap(size_t N, V, K)
    {
        void insert(Tuple!(V, K) t){ _set.insert(t); }

        V opBinaryRight(string op, T)(T key)
            if(op == "in")
        {
            auto idx = map!"a[1]"(_set.items[]).countUntil(key);
            return idx < 0 ? V.init : _set.items[idx][0];
        }
        private:
            SmallSet!(N, Tuple!(V, K)) _set;
    }


P.S. Sorry that the code for Trie itself isn't presented, but you can find the the whole thing in my Phobos fork:
https://github.com/blackwhale/phobos/blob/gsoc-uni/std/uni.d

-- 
Dmitry Olshansky

04.06.2012 13:46, Dmitry Olshansky написал:
> enum keywords = [
>              "abstract",
>              "alias",
>              "align",
>              //...  all of them, except @ ones
>              "__traits"
>      ];

A nitpick: constant arrays should be defined as `immutable` instead of `enum`. `enum` means every time `keywords` used a new mutable array is dynamically allocated:
---
auto x = keywords;
auto y = keywords;
assert(x !is y); // passes
x[0] = ""; // legal, its mutable
---

-- 
Денис В. Шеломовский
Denis V. Shelomovskij

On 6/4/12 4:46 AM, Dmitry Olshansky wrote:
> Cross-posting from my GSOC list as I think we had a lack of D rox posts
> lately :)
[snip]

I think it would be great if you converted this post into an article.

Andrei

On 04.06.2012 18:19, Andrei Alexandrescu wrote:
> On 6/4/12 4:46 AM, Dmitry Olshansky wrote:
>> Cross-posting from my GSOC list as I think we had a lack of D rox posts
>> lately :)
> [snip]
>
> I think it would be great if you converted this post into an article.
>
> Andrei
>

Sounds good, will do once I fix few issues that were mentioned (bit-packing, GC types etc.)

-- 
Dmitry Olshansky

On 04.06.2012 16:15, Denis Shelomovskij wrote:
> 04.06.2012 13:46, Dmitry Olshansky написал:
>> enum keywords = [
>> "abstract",
>> "alias",
>> "align",
>> //... all of them, except @ ones
>> "__traits"
>> ];
>
> A nitpick: constant arrays should be defined as `immutable` instead of
> `enum`. `enum` means every time `keywords` used a new mutable array is
> dynamically allocated:
> ---
> auto x = keywords;
> auto y = keywords;
> assert(x !is y); // passes
> x[0] = ""; // legal, its mutable
> ---
>

Thanks, the mutable part is then a consequence of being another rvalue.
Obviously table should have been immutable.


-- 
Dmitry Olshansky

On Monday, 4 June 2012 at 15:35:31 UTC, Dmitry Olshansky wrote:
> On 04.06.2012 18:19, Andrei Alexandrescu wrote:
>> On 6/4/12 4:46 AM, Dmitry Olshansky wrote:
>>> Cross-posting from my GSOC list as I think we had a lack of D rox posts
>>> lately :)
>> [snip]
>>
>> I think it would be great if you converted this post into an article.
>>
>> Andrei
>>
>
> Sounds good, will do once I fix few issues that were mentioned (bit-packing, GC types etc.)

Would be interesting to see some more examples, along with rationale/motivation for various aspects of your API, and possible usage scenarios.

Tries are fundamental (both data structures and respective algorithms) for lookup problems, in the same way as arrays are fundamental for indexed access.

For example, they have several advantages over hash tables. Hash calculation requires const * key.length operations, which is equivalent to the number of comparisons needed for trie lookup. But hash tables may be less space efficient, or lead to hash collisions which increase lookup time. Also, 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.

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 :)

Below are some notes related to my DCT use cases.

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?

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). 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).

I wanted to analyse your regex implementation, but that's not an easy task and requires a lot of effort... 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.

On Monday, 4 June 2012 at 12:15:33 UTC, Denis Shelomovskij wrote:
> 04.06.2012 13:46, Dmitry Olshansky написал:
>> enum keywords = [
>>             "abstract",
>>             "alias",
>>             "align",
>>             //...  all of them, except @ ones
>>             "__traits"
>>     ];
>
> A nitpick: constant arrays should be defined as `immutable` instead of `enum`. `enum` means every time `keywords` used a new mutable array is dynamically allocated:
> ---
> auto x = keywords;
> auto y = keywords;
> assert(x !is y); // passes
> x[0] = ""; // legal, its mutable
> ---

Well, in my case they were only used for mixin code generation (IIRC). Dmitry obviously has a different situation.

On 04.06.2012 22:42, Roman D. Boiko wrote:
> On Monday, 4 June 2012 at 15:35:31 UTC, Dmitry Olshansky wrote:
>> On 04.06.2012 18:19, Andrei Alexandrescu wrote:
>>> On 6/4/12 4:46 AM, Dmitry Olshansky wrote:
>>>> Cross-posting from my GSOC list as I think we had a lack of D rox posts
>>>> lately :)
>>> [snip]
>>>
>>> I think it would be great if you converted this post into an article.
>>>
>>> Andrei
>>>
>>
>> Sounds good, will do once I fix few issues that were mentioned
>> (bit-packing, GC types etc.)
>
> Would be interesting to see some more examples, along with
> rationale/motivation for various aspects of your API, and possible usage
> scenarios.
>
> Tries are fundamental (both data structures and respective algorithms)
> for lookup problems, in the same way as arrays are fundamental for
> indexed access.
>
> For example, they have several advantages over hash tables. Hash
> calculation requires const * key.length operations, which is equivalent
> to the number of comparisons needed for trie lookup. But hash tables may
> be less space efficient, or lead to hash collisions which increase
> lookup time. Also, 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.

>
> 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)
	- 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
	- extra levels ain't that bad as they look, since memory is close anyway.
	
>
> Below are some notes related to my DCT use cases.
>
> 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.
The problematic thing with one by one - say you want to stop early, right?
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?).

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.

>
> 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)

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!)

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)

> 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 ;)

-- 
Dmitry Olshansky

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

[snip]
>> 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.
>

Sorry my Trie implementation focused on "constructe once - read everywhere" case. Like I noted mutation is not hard but it's easy to blow up size if used unknowingly.
I think along the lines of:

auto trie = ...;//create it
for(...)
{
	trie[x] = ...;//modify repeatedly
}
trie.compact();//redo same algorithm as during construction, O(N^2)

>>> 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?

See above. Price is paid every time you want squeeze it in as little memory as possible by removing duplicate pages.
>
>> - 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?
>
Easy say you have 2-level 4 entry each level (for sake of simplicity), say the final value is int.

Then in highly redundant or just when there is little amount of values in initial data set (both cases are equivalent, thus tries are easily invertible btw):

LVL 0: [0, 1, 0, 0]
This first one always occupies full size (it's asserted that there is no index >= 4)
LVL 1: [0, 0, 0, 0] [1, 0, 2, 3]
Note again - only full pages, no cheating and half-pages, but we can save on the amount of them (note almost obligatory zero page)

So it contains only 1, 2 and 3 at indexes of 4, 6, 7 respectively, T.init is our way of not EXISTS ... yes, I think that should be user definable.
This way there is no checks anywhere, only shift, add dereference, shift, add, dereference...

>> 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.

That and some simple minded hashing of say first char and the length ;)
In any case you need to munch the whole symbol, I think.

> For example, one by
> one would allow ignoring key encoding (and thus using multiple encodings
> simultaneously just as easily as single).

It's just as easy with the whole thing. Treat it as bytes ;)

>
>> 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?
>

No I meant stopping on say 2 level of 5 level Trie because the element was not found. Stupid idea generally.

>> 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.

It could enlightening just don't give up too quickly and don't jump to conclusions. In fact try to be sympathetic with "loosing party", like in ... "hm this way is much slower, so bad - I have to optimize it somehow". In other words make sure you squeezed all you can from "slow" method.

>> 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.

Compare with C's memchr and such just in case, it was ~4x faster then Phobos find last time I checked.

>>> 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?

Well I might recompile regex to use binary search vs Trie again, off the record it was ~2 times slower minimum. That was sorted array vs oldish Trie, note however that it's responsible for only ~40% of actual time of matching... so it's around 2.5 * 2 = 5

Compiler's switch I *believe* could be at least ~2x better as it's fully unrolled binary search,
but hard to guess at how much actually and it depends on the CPU model by the end of day.
The older CPU the better lookup tables generally are, except these Celeron mules with half the cache ;)

-- 
Dmitry Olshansky