News for hackers. Stuff that matters.
Re:The ups of downs of porting 50k lines of C++ to Go by Loic on Saturday March 07, 2015 @05:31AM (#9161533)
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

Re:The ups of downs of porting 50k lines of C++ to Go by danieldk on Saturday March 07, 2015 @05:47AM (#9161558)
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

Re:The ups of downs of porting 50k lines of C++ to Go by Loic on Saturday March 07, 2015 @06:48AM (#9161630)
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

Re:The ups of downs of porting 50k lines of C++ to Go by eric_bullington on Saturday March 07, 2015 @06:19AM (#9161595)
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.

Re:The ups of downs of porting 50k lines of C++ to Go by logicchains on Saturday March 07, 2015 @05:47AM (#9161559)
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.
Re:The ups of downs of porting 50k lines of C++ to Go by stingraycharles on Saturday March 07, 2015 @06:43AM (#9161620)
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...

Re:The ups of downs of porting 50k lines of C++ to Go by logicchains on Saturday March 07, 2015 @06:58AM (#9161643)
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.

Re:The ups of downs of porting 50k lines of C++ to Go by scottlamb on Monday March 09, 2015 @08:24PM (#9175090)
> 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.

Re:The ups of downs of porting 50k lines of C++ to Go by dsymonds on Saturday March 07, 2015 @10:49PM (#9164437)
FYI, if you don't need required/optional, non-zero defaults and extensions, try `syntax = "proto3"`. It generates much better Go code.
Re:The ups of downs of porting 50k lines of C++ to Go by whyever on Saturday March 07, 2015 @06:11AM (#9161584)
How can you have a POD struct without pointers if one of your fields is a string?
Re:The ups of downs of porting 50k lines of C++ to Go by logicchains on Saturday March 07, 2015 @06:28AM (#9161604)
Couldn't it be done with a fixed-size array of runes or bytes? It's definitely possible in C/C++.
Re:The ups of downs of porting 50k lines of C++ to Go by z92 on Saturday March 07, 2015 @09:08AM (#9161837)
Not without wasting a lot of space depending on the difference between average size of string vs maximum size of string.
Re:The ups of downs of porting 50k lines of C++ to Go by logicchains on Saturday March 07, 2015 @07:28PM (#9163811)
We generally know the maximum string sizes for each property, and they're pretty small, so this wouldn't have been a problem.
Re:The ups of downs of porting 50k lines of C++ to Go by a8da6b0c91d on Saturday March 07, 2015 @09:36AM (#9161878)
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.
Re:The ups of downs of porting 50k lines of C++ to Go by masklinn on Saturday March 07, 2015 @09:08AM (#9161838)
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.

Re:The ups of downs of porting 50k lines of C++ to Go by stcredzero on Saturday March 07, 2015 @12:51PM (#9162458)
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.)