How Unix spell ran in 64kb RAM
blog.codingconfessions.com
How Unix spell ran in 64kb RAM
1–10 of 53 posts
Re: How Unix spell ran in 64kb RAM
#2Ah, the Good Old Days. Back when a bit of memory cost more than most butter churns, and the ultimate data transfer technology was a sharp Express rider with his saddlebags full of punch cards...
Back in the early 1980's, I recall futzing around a bit with dictionary compression algorithms. Very interesting - but it didn't take me long to conclude that outperforming `spell` wouldn't be easy. Nor worth the effort.
Re: How Unix spell ran in 64kb RAM
#364kB was huge. The first version of UNIX needed 24kB (half of which was taken by the kernel).
Re: How Unix spell ran in 64kb RAM
#4Marginally related... has anyone ever ported the "typo" program to modern C?
Re: How Unix spell ran in 64kb RAM
#5Marginally related... has anyone ever ported the "typo" program to modern C?
For reference, https://github.com/robpike/typo/blob/master/unix/typo.c
Re: How Unix spell ran in 64kb RAM
#6Way too smart for worse is better. Think Worser!
The main memory bandwidth and the disk bandwidth were about the same, a little of 1MB/s.
I would have done this in multiple passes (but still used the Bloom Filters, those are cool).
https://github.com/arnoldrobbins/v10spell
https://code.google.com/archive/p/unix-spell/
The original paper is great https://www.semanticscholar.org/paper/Development-of-a-Spell...
It is hosted on his web page https://www.cs.dartmouth.edu/~doug/
https://en.wikipedia.org/wiki/Douglas_McIlroy
If you are a word nerd, you will have found obovate and there, this chart.
https://upload.wikimedia.org/wikipedia/commons/e/e8/Leaf_mor...
Re: How Unix spell ran in 64kb RAM
#7in the mid 80's i ran into something similar. Fast is relative.
I had a lot of data, 640KB RAM, 64KB of heap, and 64KB of stack. I had hundreds of megabytes that I had to search extract data from and then combine some of them.
I experimented with data index structured into ternary trees. Conceptually it made sense, but implementation-wise the relationships and paths were still too big to keep in 64KB.
Instead of compression, I did swapping. I wrote a TSR (think service), a piece of code that would process a chunk of the data, extract the results, store it n the stack, dump the original data, make an interrupt call to the TSR, which in turn destroy the heap, and read in the next chunk from storage, return control to the program, process, combine with stack data, and continue until finished the entire process.
Originally this process took about a week for three data entry persons (think about a dozen 3" ring binders filled with tables), and an specialist combining the information. The program completed the work in just a few hours. It was amazingly "fast".
This was on a single threaded system.
[0] https://en.wikipedia.org/wiki/Terminate-and-stay-resident_pr...
Re: How Unix spell ran in 64kb RAM
#8I had spelling checkers on the Apple ][ that ran in 48K!
Re: How Unix spell ran in 64kb RAM
#9This spell check must have come later. The original spell check burst the words of the document, and sort -u'd them:
makewords sentence | lowercase | sort | unique | mismatch
Re: How Unix spell ran in 64kb RAM
#10I wonder what common typos this misses thanks to the hashing?
Related, a contest about compressing the Wordle dictionary: http://golf.horse/wordle/