Comment by Loic | Hacker News Reader

Comment by Loic | Hacker News Reader

Parent Full thread

Effectively, you need to keep a small heap and if possible have "simple" data structure. In my case, I implemented the Python code of a trie based levenshtein distance algorithm[0]. I used maps because it was basically a direct translation of the Python code. This resulted in millions of maps and oft the index would just stop in the garbage collector for a couple of seconds. I solved it using my own map which is travelled linearly.

    type SpellCheckerMap struct {
        Runes []rune
        Nodes []*SpellCheckerNode
    }

with only few runes, I can just go through the list to find the index of the following node. You save the computation of the map hash key. It is pretty fast, here is an example of a spelling suggestion over a 500,000 words corpus[1].

Basically, the garbage collection cost forced me to think about a better data structure for my case. Maybe not that bad all in all.

[0]: http://stevehanov.ca/blog/index.php?id=114 [1]: https://www.chemeo.com/search?q=asparine

Semi-offtopic:

The are more compact representations, e.g. you can store the dictionary in a deterministic acyclic minimized finite state automaton (which can be stored in a flat array/slice). This gives you O(n) time lookups, where n is the length of the word, and reduces much of the redundancy in a dictionary.

Words within an edit distance can be found by computing a Levenshtein automaton for the word (which can be done in linear time) and computing the intersection language of the dictionary automaton and the Levenshtein automaton.

This approach is fast and very compact. I have a Java implementation:

https://github.com/danieldk/dictomaton

Oh, this is very cool. I wonder how many CAT (Computer-Aided Translation) tools out there (many of which are notoriously slow) could be significantly sped up using this approach.

I'd bet most of them, although they're almost all closed-source so we will likely never know.

I am a chemical engineer so reading "deterministic acyclic minimized finite state automaton" is sending me back in my first years at university. As I want to implement instant search with part of string matching, this can be very interesting. This is to match "Octane, 2,4,6-trimethyl-" when typing "trimethyl".

For the moment I am looking at the Linkedin approach[0]. Sorry for keeping this semi-offtopic thread alive, but these problems are so interesting that I cannot stop.

[0]: https://github.com/jamra/gocleo

One issue is that the server uses Google Protocol Buffers. The following definition, for instance:

    message Foo {
	required string a = 1;
	required int32 b = 2;
	optional int64 c = 3;
    }

Generates a struct like:

    type Foo struct {
        a *string
        b *int32
        c *int64
    }

This is not particularly friendly to the garbage collector compared to a POD struct with no pointers.

How can you have a POD struct without pointers if one of your fields is a string?

Couldn't it be done with a fixed-size array of runes or bytes? It's definitely possible in C/C++.

Not without wasting a lot of space depending on the difference between average size of string vs maximum size of string.

You can use a string class like the one in Folly that decays from a fixed array to heap allocated space if the string gets too long.

We generally know the maximum string sizes for each property, and they're pretty small, so this wouldn't have been a problem.

I believe it's also possible to use variable-size arrays in C or C++ (and end up with a variable-size struct).

Go does allow fixed size arrays in structs, and they're inline in the struct, so `struct { foo [8]uint }` is 32 bytes, whereas `struct { foo []uint }` is 12 bytes and `struct { foo string }` is 8.

Protocol buffers allows you to reuse the memory of your objects. You can simply reuse the object where you parse your message into. You pool these objects, and you just saved yourself a huge amount of heap allocations.

https://developers.google.com/protocol-buffers/docs/referenc...

This would work if we were only using them for messaging, but the protobuffer objects are also used as the datastructure in which the information they contain is stored. This was done in the name of simplicity, to avoid creating a separate internal datastructure for each kind of message.

The flow of data is currently:

various external sources -> merged into protocol buffer struct -> later sent to client

To avoid keeping a heap of protocol buffer structs in the heap, this would need to change to:

various external sources -> merged into some internal datastructure -> later converted into protocol buffer struct and sent to client.

> This would work if we were only using them for messaging, but the protobuffer objects are also used as the datastructure in which the information they contain is stored. This was done in the name of simplicity, to avoid creating a separate internal datastructure for each kind of message.

Did you consider keeping strings (serialized messages) in your cache rather than message objects? I do this in C++ code simply for memory efficiency. Here it would also allow you to avoid these extra pointers.

FYI, if you don't need required/optional, non-zero defaults and extensions, try `syntax = "proto3"`. It generates much better Go code.

Lots of small maps becoming little arrays. The more things change, the more they stay the same. (There is production Smalltalk code from the late 80's running in large multinationals that's basically what you just described.)

Reply on news.ycombinator.com