IssueRaiser

Basically all the data fit in the CPU cache True, but it's the relatively-slow L3 cache (the L2 cache is at most 1MB for the processor ...

Basically all the data fit in the CPU cache True, but it's the relatively-slow L3 cache (the L2 cache is at most 1MB for the processor being used for testing). I think the biggest problem with this trie implementation is the amount of pointer-chasing due to the low branching factor. The step function does four (!) loads for every character, each depending on the result of the previous load. Real tries have much larger branching factors (and compress each node to avoid wasting tons of memory).

Posted by panic on Jun 29, 2015, 8:38 PM

Tags

Related issues

Raise real-world problems, find people facing the same issue, and discuss solutions.5,500 issues0 comments

hackernews (Other)

Basically all the data fit in the CPU cache True, but it's the relatively-slow L3 cache (the L2 cache is at most 1MB for the processor ...

panicJun 29, 2015, 8:38 PM

Basically all the data fit in the CPU cache True, but it's the relatively-slow L3 cache (the L2 cache is at most 1MB for the processor being used for testing). I think the biggest problem with this trie implementation is the amount of pointer-chasing due to the low branching factor. The step function does four (!) loads for every character, each depending on the result of the previous load. Real tries have much larger branching factors (and compress each node to avoid wasting tons of memory).

Comments (0)

No comments yet. Start the discussion.

Comment on this issue