[ This post is mostly meant for Jarlve ]

First off, I’m very impressed with your AZdecrypt software Jarlve! I’ve only read a bit of the forum so far so I’m not totally clear on how you’re implementing beam search or exactly how you’re generating and scoring candidate solutions, but I can certainly appreciate the results. Your integration of so many transformation and batching options is great too. Thanks for creating, sharing, and maintaining such a wonderful tool!

I’ve been using it a bit the past few weeks and besides the great results, I’ve also noticed a couple things that could probably give it dramatically faster loading and processing times.

(Of course, forgive me if my advice isn’t quite right. I’m obviously making many assumptions about how things are done in your code without having it in front of me. And I’m mainly a C/C++/python developer. So I spent a few days re-learning BASIC so I could describe these modifications. But please forgive if my FreeBASIC has syntax errors or something like that. I’m an experienced programmer and my general advice is correct — but if you see anything fishy with my FreeBASIC presentation, it’s probably a mistake and not something clever.)

FWIW, this feedback comes mainly because I’ve been building my own ngram files with a ~3TB corpus. That’s how I’ve run into these performance bottlenecks. I’m definitely glad your ngram format is so transparent and easily extensible. Hopefully I can share the files I’m building if anyone here is interested.

Anyway, it seems obvious that AZdecrypt allocates a full, flat array for the entire keyspace of each ngram it works with.

1-4 grams: This is a great choice. All the entries in these arrays have at least some weight. And these tables are small, fast, and easy to implement.

5-grams: Still an OK choice. To be fair, a large enough corpus can literally fill 100% of all possible 5-grams with non-zero logarithmic weight.

But let's consider the density of your largest Reddit n-gram files:
5-grams: 74.4%   =    8,834,667   / 11,881,376
6-grams: 25.1%   =    7,544,234   / 308,915,776
7-grams: 2.0%	 =  165,568,040   / 8,031,810,176

Or even my currently densest n-gram files:
5-grams: 100.0%  =   11,881,376   / 11,881,376
6-grams: 37.1%   =  114,659,798   / 308,915,776
7-grams: 2.3%	 =  188,212,577   / 8,031,810,176
8-grams: 0.07%   =  151,397,312   / 208,827,064,576

I saw over on the FreeBasic forum that you’re implementing your own trie to reduce memory consumption?? That’s incredibly metal! You must be learning a lot! But while it’s definitely impressive, it does make me wonder.

As you may know, a programmer’s three greatest virtues are laziness, impatience, and hubris. I definitely respect the hell out of your hubris. I’m too wizened and weary to implement my own trie. But one programmer to another, I do question your lack of laziness and impatience. Where is your commitment to the 1st and 2nd virtues?? Don’t you want AZdecrypt to run faster?? Don’t you want to do less of your own programming??? There’s a lazier and more impatient version of you trapped within. Reach deep. You can summon him. I believe.

Incidentally, the guys over on the FreeBasic forum giving you advice have amazing intuitions. Who suggests Judy Arrays?! Like, for anything?? As an outsider to your community over there, I wouldn’t have imagined FreeBASIC programmers just casually dealing in such obscure, hyper-optimized data structures.

But even as someone who shares your unhealthily high interest in the pure, platonic ideal of programming your own Judy Arrays, I can’t help but wonder that if the guys over on the FreeBASIC forums who suggested those and trie’s to you might have nudged you in a slightly less esoteric and less theoretically maximally pure direction if they had realized just how sparse your data sets truly are (especially as n-gram size increases).

Sure, 1-5 grams can get (approximately) fully filled. But even the fattest 6-gram file should never contain over half of the total keyspace. Even if you stream the library of congress thru it.

[ As an aside, most 6+ grams should be even sparser in theory than they end up being in practice. To understand why, imagine isolating all the "validgrams" in a keyspace — the set of all ngrams that can be reached by combining any number of English words. For instance, GAME + LOVER can form AMELO (a 5-valid-gram). But no combo of English words can reach XTQQZ. Even with the most liberal dictionary files that include most proper nouns, names, misspellings, Briticisms, etc… you still only end up with ~40% of the key space being validgrams at n=6… and less than 9% at n=7! I haven’t calculated 8-gram validgram density yet. It’s a touch more complicated to calculate but totally doable. Maybe once 8-grams become more usable, I’ll characterize that keyspace too and write up another post about it?]

Anyway, the best part about the flat array structure you’re using right now (beyond simplicity and raw lookup speed) is how you "save" memory by not storing the ngrams themselves. You implicitly store ngrams as the index into your array by enumerating your keyspace in a logical, sequential fashion. It looks like you’re already ennumerating ngrams –> unsigned longs which is great.

And this strategy works wonderfully up thru 5-gram (and maybe even 6-grams). But it’s sluggish on 7-grams and can’t function at all on 8-grams unless you have 200GB of memeory. And even with 200GB of memory, I still need almost an hour to load an 8-gram file and then the cycle times are much too slow to be practical.

But a quick fix to make the current 8-gram implementation usable (assuming you have over 200GB of ram) and to speed up all the smaller grams as well is to simply allocate the memory more intelligently.

I noticed you posted this test harness version of your lookup table over on the FreeBASIC forums:

type nv
   ngram as ulongint
   score as ubyte
end type

dim as ulongint h,i,j,k,r,s
dim as ulongint lookups=10000
dim as ulongint array_size=1000000 'up to 500,000,000
dim shared as nv array(array_size)

—
Quick memory fix for 6-8 grams
—

Based on this and also the loading speed of 8-grams (and even 6 / 7 grams), it’s likely you’re not allocating your own memory for the array off the heap. Instead, FreeBASIC is allocating you memory off the stack. Obviously, you’re specifying the array size, but there are multiple ways to do memory allocation and the default one (which works well for 99% of cases) is unfortunately the least efficient when you’re dealing with really large chunks of data. If you don’t work with big data, this sort of memory management quirk doesn’t really come up.

It’s kind of inside baseball for programmers but the big problem with this is that FreeBASIC is going to end up doing two very wrong things:

1) FreeBASIC will allocate all your array memory on the stack. Stack memory is typically limited to 1MB / process. Exceeding this limit normally crashes programs. But sometimes it’s only slows them down to a crawl as a compromise between that and crashing. The OS’s memory manager is crying on the inside as this happens (it’s quiet but you can hear it if you listen close). It’s sort of a miracle this much memory allocation off the stack succeeds at all. It’s probably a combination of FreeBASIC being slow enough and Windows being forgiving enough to allow this combo. If I did this with C / Linux, it would almost certainly allocate stack so fast that Linux would (mercifully) segfault to warn me that something was going wrong. This is probably also related to why you mentioned somewhere that ngram files should only have < 1MB per line. Why? Is it because AZdecrypt sometimes hangs or crashes if that limit is exceeded? That’s likely another manifestation of the same issue where stack memory grows too fast or too large and the OS panics and throttles everything super slow as the file buffer continuously overflows and gets automatically re-allocated over and over by FreeBASIC’s memory management. (You could make load times much faster and remove this 1MB limitation by manually allocating your own file buffer. It’s a 2 line fix. I’ll mention other tweaks along with this in my next post.)

2) FreeBASIC won’t actually give you all the memory you ask for by default. For example, currently, when you ask for 1,000,000 nv elements, behind the scenes, FreeBASIC actually only allocates you 1 page of memory and gives you a pointer to it. That’s 4kb ~ aka 56 nv structures. So when you insert the 57th element in your array, FreeBASIC interrupts your program for 10,00-100,000x CPU cycles to grab you a 2nd page of memory. I’m not positive how pathologically bad FreeBASIC’s default stack allocation algorithm is, but most languages have atrociously naive stack expansion strategies (since they are used so infrequently by "normal sized" programs). It’s likely that a mere 50MB 8-gram is currently being interrupted 3.7 billion times while it slowly loads 99.93% zeros into a ~200GB chunk of memory, 56 ngrams at a time.

Amazingly, the simplest way to fix this in FreeBASIC only requires 3 extra words[!]:

dim shared as nv array(array_size)


--- should become ----


Redim shared as nv array(array_size)

... '' process array

Erase array              

See the post below on the FreeBASIC forum for more color on this issue. It also includes three other, slightly more complex options for implement your own memory management which should also fix this stack / resizing issue. I expect one of these methods will work and give a brisk speed up, but just to be clear, I don’t actually use FreeBASIC regularly and haven’t personally tested this. So one of the other methods could possibly end up working better:
https://www.freebasic.net/forum/viewtopic.php?t=26709

Apologies for the long post. This only fixes the simplest performance bottleneck I found. I’ve also figured out and written up a solution to let ngram files load 5-20x faster and found two drop in replacements for your array structure that hold the 7/8 gram arrays in FreeBASIC with substantially less memory and presumably better processing velocity. The processing speed up will be roughly proportion to data sparsity, so on the order of ~5-10x less memory and some correlated speed of that size for 7-grams, and ~500-1000x less memory usage and a similar fraction of processing speed up for 8-grams. Happy to post those solutions too if there’s interest.