Re: [computer-go] SGF parsers

[Paul Pogonyshev <pogonyshev@xxxxxxx>]

Darren Cook wrote:
> > Sen:te Goban's parser is based on an optimized version of sgf.c by Antti
> > Huima. It takes 36 seconds to read the 20300+ files, ~40MB of a GoGoD
> > distribution, to build the trees in memory and to create game record
> > references that include the number of moves and the game signature.
>
> How much memory does the tree use once in memory?
>
> I'm disappointed with my SGF parser (built using Spirit library for C++) as
> I found there were trade-offs in ease of writing, speed of parsing, size
> (overhead) of data structures, and ease of using it to actually do things
> with the game data. I kept changing my mind as I wrote it so I have a mess
> that fails on all 4 criteria :-(.

(I'm replying, since I guess you are not interested specifically in
Goban's parameters.)

So, here it is 24 bytes per node, 12 bytes per property, plus of course
extra memory for complicated property values (text or position lists,
like those of AB[].)  All nodes and properties are stored in chunks of
128 items at once with O(1) allocating and O(1) freeing.  This reduces
the number of calls to malloc()/free() which is very important with huge
trees.

I consider my SGF library to be very good on all four your parameters
and very bad on complexity (i.e. the code is _very_ complex, specifically
the parser.)  The parser can also handle certain misformed input (as per
SGF FF[4] specification) and validate files.

Paul

_______________________________________________
computer-go mailing list
computer-go@xxxxxxxxxxxxxxxxx
http://www.computer-go.org/mailman/listinfo/computer-go/