Last time we drastically sped up our program by changing how we put lists together. This time we’re going to speed things up again by changing how we take them apart.
Speed Reading A List
The part of our code that creates compressed bit lists now runs super fast but our program as a whole is still very slow. That suggests we’ve got a problem in the part of the compression function that actually writes to output. If you look at the code you’ll notice that we write to output eight bits at a time by using a series of subsequence copies and assignments. This was nice because it perfectly matched the idea in our heads (read 8 bits from the front of the list and then throw them away).
The problem here is that subseq can get pretty expensive, especially when used to grab really big subsequences from really big lists. In particular the way that we delete used bits from our bitlist is pretty horrible since we aren’t actually deleting them; instead we basically ask subseq to make a brand new copy of everything in the list except the first eight items. We then replace our original list with this slightly shorter list. This obviously does work but all that copying is reaaaalllly slow. Is there any way we can get the same effect but avoid all that work?
Well, when you think about it as long as we only read each bit once it doesn’t really matter whether we delete them after we use them or if we just leave them alone but ignore them. Kind of like a book. You don’t rip out pages after you finish reading them, you just use a bookmark to keep track of which pages you have and haven’t read.
Is it possible that we can do the same thing with our data and write some code that reads through our list eight bits at a time without deleting any of the old stuff?
Of course we can! It’s not even terribly hard. The mighty Lisp loop macro can actually be configured to read multiple values at a time and then skip forward multiple values to get its next input.
(defun white-rabbit-compress-file (input-filename output-filename) (let ((bitlist (compress-terminate-and-pad-file input-filename)) (out (open output-filename :direction :output :element-type '(unsigned-byte 8)))) (when out (loop for (b1 b2 b3 b4 b5 b6 b7 b8) on bitlist by (lambda (x) (cddddr (cddddr x))) do (write-byte (8-bit-list-to-byte (list b1 b2 b3 b4 b5 b6 b7 b8)) out))) (close out)))
As you can see we’re asking the loop for eight variables at once instead of just one and we’re telling it to skip forward multiple spaces at once by using a local lambda function that uses some weird syntax to basically look for the fourth neighbor of the fourth neighbor of our current list item. So now we read eight bits from our list, jump forward eight spaces and then repeat till we’re done.
What does that do for our runtime?
[100]> (time (white-rabbit-compress-file “chapter1.txt” “bettertimedoutput3”))
Real time: 0.44549 sec.
Run time: 0.436 sec.
Space: 3931184 Bytes
GC: 3, GC time: 0.036 sec.
T
Look at that! Half a second processing time and only 4 megabytes of memory usage now that we aren’t wasting all our time and RAM making copies of copies of copies of subsequences of copies of our copied data copies.
In fact, at this speed we can finally achieve our goal of compressing the entirety of Alice in Wonderland!
[102]> (time (white-rabbit-compress-file “aliceASCII.txt” “tinyalice”))
Real time: 5.921212 sec.
Run time: 5.872 sec.
Space: 52589912 Bytes
GC: 16, GC time: 0.86 sec.
T
For anyone who cares we managed to shrink it from 147.8 kilobytes to 113.3, which is roughly 25% smaller just like we hoped for. Go us!
Making More Functions Fast
As long as we’re in our groove it might be nice to also speed up our decompression function, especially since I’m getting pretty tired of having to wait five minutes every time I want to test whether or not a change to compression logic actually worked.
Like compression our decompression is a two step process. The white-rabbit-decompress-file function starts by calling the file-to-bitlist function to get a compressed file full of bits and then it goes on to decompress those bits and write them to our output file.
These two functions have the same efficiency flaws that compression functions did. file-to-bitlist relies too much on append and white-rabbit-decompress-file abuses subsequences.
Cutting the appends out of file-to-bitlist isn’t any different than it was for our compression function. Replace the appends with pushes to efficiently create a backwards list and then flip it around.
(defun file-to-bitlist (filename) (let ((bitlist '()) (in (open filename :element-type '(unsigned-byte 8)))) (when in (loop for testbyte = (read-byte in nil) while testbyte do (let ((bits (byte-to-8-bit-list testbyte))) (loop for i in bits do (push i bitlist)))) (close in)) (nreverse bitlist)))
Fixing up the way we write to output is going to be a little bit harder. Since we’re working with a compressed file we can no longer safely say that all of our letters are eight bits long. Some letters will actually only be four bits long and others will be nine bits long. So we can’t just write a loop that always jumps n items forward between writes. Instead we’re going to have to write our own looping logic that’s smart enough to decide when to jump forward four spaces and when to jump forward nine.
The basic idea is that we will start with a variable pointing at the start of our list. We will then use subseq to check whether the list starts with a 0 or 1 (a short subsequence at the start of a list is pretty cheap). Like usual we will use this information to decide how to decompress our data. We will then manually change our variable to point either four neighbors further or nine neighbors further as needed. This will make that new spot look like the start of the list and we can just loop until we hit the termination sequence.
(defun white-rabbit-decompress-file (input-filename output-filename) (let ((bitlist (file-to-bitlist input-filename)) (decompressing 1) (out (open output-filename :direction :output :element-type '(unsigned-byte 8)))) (when out (loop while decompressing do (if (= 0 (first bitlist)) (progn (write-byte (gethash (subseq bitlist 0 4) *list-to-byte-compression-hash*) out) (setf bitlist (cddddr bitlist))) (if (equal (subseq bitlist 0 9) '(1 0 0 0 0 0 0 0 0)) (setf decompressing nil) (progn (write-byte (8-bit-list-to-byte (subseq bitlist 1 9)) out) (setf bitlist (cdr (cddddr (cddddr bitlist))))))))) (close out)))
Once again we use a chain of cdr and it’s subtypes to jump through our list. Since this is the second time we’ve used them we might as well explain them.
Remember how I said every item in a Lisp list is made of two halves? The first usually* holds a piece of data and the second usually holds a link to the next item in the list. Together these two halves make up a “cons cell” and you can individually access each half using the historically named car function to grab the first half and cdr to grab the second half. Since the second is usually a link to the next item in the list cdr
You can walk through lisp lists by chaining these together. If you want the data at the third spot of the list you need to cdr to get to the second item then cdr again to the third item and the car to get the data, or in other words (car (cdr (crd list-with-cool-data))).
On the other hand if you want a new sublist that starts at the third part of the list you would just use two cdrs to get the link to the third item without using car to then specifically grab only the data.
Nesting these calls can get annoying though so Lisp has several build in functions that condense several chains into single function such as caddr or cddr. Unfortunately these only go up to four calls in a row which is why in order to jump the start of our list forward nine spaces we still have to chain multiple calls together.
Now that you understand how the code works let’s see how well it works:
[2]> (time (white-rabbit-decompress-file “tinyalice” “fastexpandtest.txt”))
Real time: 5.585598 sec.
Run time: 5.268 sec.
Space: 51634168 Bytes
GC: 20, GC time: 0.608 sec.
T
We can now decompress files just as fast as we compress them. It’s not exactly a great program but for an educational toy I think it turned our pretty well. And hopefully you learned at least a little about Lisp’s inner guts and what to look for when things seem slow.
* Sometimes the first and the second halves of a cons cell will both hold links to other cons cells, allowing for nested lists and interesting tree data structures.