Gaddag optimization

ericlang · December 15, 2024, 9:21am

A little related tail to this… I am using the “gaddag” structure in my program, which takes around 100 MB in memory.

The makers of the macondo scrabble engine say that their gaddag fits in around 5 MB. Some words about the structure are here:

github.com

andy-k/wolges/blob/6d9c6a631d52f596dc0b79e67490c7fb4aa96131/details.txt#L89


      
          
          - Casting true/false to integer gives 1 and 0.
          - In two's complement, -1 has all bits set, use it with bitwise-and.
          - Right-shifting a signed integer copies the sign bit.
          - Blank tile on board has high bit set. Blank tile on rack is 00.
          - Cross set bit 0 (adjacency) toggles perpendicular word multiplier.
          
          
          DATA STRUCTURE
          
          alphabet defines tile numbers. Tiles are numbered consecutively from 01. Tile
          00 is reserved and may mean different things. By convention, 00 on rack means
          blank. High bit is set when blank is played, so 81 means 01 played as a blank.
          Tile labels are strings, so multi-codepoint labels are possible. This module
          does not define how strings are parsed into tiles as that is a
          non-deterministic process in the general case and is only useful when building
          the word graph.
          
          bag stores a bag. A new bag is sorted, shuffle it first. Tiles are drawn by
          popping from the end. When putting back tiles each returned tile is inserted at
          a random position but the rest of the bag maintains the original order.

I cannot follow and or believe if you add nodes in “gaddag” way this fits in 5 MB for lets say 250.000 words.
(The word CARE would be entered here as ERAC, RAC@E, AC@RE, C@ARE)
Does anyone understand if it is true and how?

Sze · December 15, 2024, 12:25pm

I only had a rough look at the text, but it seems very highly optimized.

Different from other implementations of similar structures, it is allowed to share the tail end of a node.

This makes me think that it may save on a lot of nodes through structural sharing.

It also seems to me that the “Kurnia Word Graph” may be a different graph and not really be a gaddag, but that is just a hunch, finding that out would require reverse engineering the code and I don’t really want to stare at rust code.

Sze · December 15, 2024, 12:39pm

I think you would have to find out how many words where actually in the word list, the word list may have been a lot smaller.

Or use your own word list to build it and see if it is way bigger with that.

ericlang · December 15, 2024, 1:26pm

I know these source lists are around 250.000 words.
And yes: I am 20 times bigger. That is why I cannot believe it. Or they use some insane completely different structure. I will have to check it out…

edit: ah, i missed your previous post. No… I also don’t want to stare at Rust. I will focus on my engine for now and keep smart gaddags for later.

sgordonphd · December 18, 2024, 11:04pm

Using standard pointers will bloat the structure. The original implementation rolled its own pointers. If memory serves from 30 years ago, 22 bits were used for pointing within its own large array, while the other 10 bits encoded other essential information. I recall having about 100K words encoded. I believe the SPE article provides lots of clues about this.

Also, there are lots of duplicate nodes, so FSA minimization is very effective.

Depending on the lexicon, 22 bit addresses might be insufficient for the unminimized version, so you may have to use standard pointers and then minimize it before hand-rolling a small structure that can easily stay in memory.

Steven Gordon, PhD