DEV Community: Rahul Jha

Daily Log 17

Rahul Jha — Tue, 06 Apr 2021 20:04:15 +0000

Started reading the chapter "Python interpreter in Python" by Allison Kaptur.

Daily Log: 13, 14, 15, 16

Rahul Jha — Mon, 05 Apr 2021 19:22:56 +0000

From my last post:

this might have to wait until the weekend.

The weekend came and went away, but this bug did not. In all honesty, I haven't gawked at the screen long enough. You know, sleeves up, pupils dilated, sight narrowed down to a beautiful 8 pixel wide monospace, and then suddenly, it occurs to you. The "flow" as some might call it.

My excuse, like the 99% of you, is time. This week again, jampacked with the final batch of backlog from the last quarter, which I don't want to carry forward. I'm also taking a little break from work (and everything else) which means a smaller week for me. I don't think that I'd be able to get back on track with "clox" right away.

The good news is that I've another something to munch on while I wait for "the flow" (I use the term, almost mockingly, despite it being a real, physiological phenomenon; to assert on spending time and doing the work and not on waiting for the flow to occur magically). This just arrived in the mailbox:

This book documents the journey of design decisions taken by experienced programmers, the likes of Guido van Rossum and Ned Batchelder, when they start working on something large (complicated) which is still small in size, a limit artificially enforced in the book, ergo 500 lines or less. from "Building a web crawler with asyncio routines" to writing a "Python interpreter in Python" under 500 lines of code.

As attractive and luring as it is, I still doubt if I'd be able to push another attractive post this week. 🤞

Daily Log: 12

Rahul Jha — Thu, 01 Apr 2021 18:54:31 +0000

This bug is turning out quite hard to squish, and I don't see an obvious place to start looking for.

Guests came over, and as usual, lots of work. New Year. New Quarter. New responsibilities. New Goals. Wish me luck!

Time crunch tomorrow as well, and I don't quite like the idea of going forward with this buggy implementation, so this might have to wait until the weekend.

Daily Log: Day 11

Rahul Jha — Wed, 31 Mar 2021 18:48:41 +0000

With trying to fixing a broken sleep cycle, productivity has plummeted quite a lot. Didn't get a whole lot of time to debug the bytecodes-executing-out-of-sequence bug.

Daily Log: Day 9 & 10

Rahul Jha — Tue, 30 Mar 2021 05:37:50 +0000

The stack we talked about in the last post is to hold intermediary values generated by our interpreter, e.g.:

  fun echo(n):
      print n;
      return n;

  print echo(echo(1) + echo(2)) + (echo(4) + echo(5));

While our interpreter is computing echo(2), it would need some space in memory to hold the output from echo(1) -- That's where the stack comes in. Similarly, it would need to store the output of echo(1) + echo(2), while it computes echo(4) + echo(5). These "produced" values are all pushed in a stack.

After implementing the stack, noticed that the order of execution of opcodes is not correct in the last output:

== Test Chunk ==
0000  122 OP_CONSANT          0 '1.2'
0002  123 OP_CONSANT          1 '456'
0004  124 OP_RETURN
0001    | OP_CONSANT          0 '1.2'
1.2
0003    | OP_RETURN
456
0005    0 OP_CONSANT          0 '1.2'

The chunk.code should look like this:

OP_CONSTANT
0 // Address of 1.2 in chunk.values
OP_CONSTANT
1 // Address of 456 in chunk.values
OP_RETURN

and chunk.values:

1.2
456

Now, notice that OP_RETURN was executed before the last OP_CONSTANT. Still debugging why.

Implementing the heart of clox's VM

Rahul Jha — Sat, 27 Mar 2021 22:13:38 +0000

Halfway through Chapter 2 of Crafting Interpreters. We are implementing a VM to "execute" the instructions we had managed to store in chunks in the last post.

So far, we've added an interpret method, which initializes the Instruction Pointer (a pointer which always points to the next instruction to execute) and calls a run method, which just keeps iterating over the vm.chunk which consists of opcodes and their operands, and runs corresponding C code. It looks like this:

InterpretResult run() {
    #define READ_BYTE() (*vm.ip++)
    #define READ_CONSTANT() (vm.chunk->constants.values[READ_BYTE()])

    for (;;) {
        uint8_t instruction = READ_BYTE();
        #ifdef DEBUG_TRACE_EXECUTION
            disassembleInstruction(vm.chunk, (int)(vm.ip - vm.chunk->code));
        #endif
        switch (instruction) {
            case OP_RETURN: {
                return INTERPRET_OK;
            }
            case OP_CONSTANT: {
                Value constant = READ_CONSTANT();
                // For now, let's just print the value
                printValue(constant);
                printf("\n");
                break;
            }
        }
    }
    #undef READ_CONSTANT
    #undef READ_BYTE
}

Not a whole lot useful, you'd say but hey, we don't have any supporting infrastructure right now. Bob tells me that this is the heart of the interpreter we are building and it will spend some 90% of its time here.

For the same "program" we embedded in our last post, this outputs:

== Test Chunk ==
0000  122 OP_CONSANT          0 '1.2'
0002  123 OP_CONSANT          1 '456'
0004    | OP_RETURN
1.2
456

Here on, I see that we're going to build a stack -- for holding values of local variables? perhaps. Let's find out!

Housekeeping announcement: I'm not really enjoying writing daily posts. Way too less time to cram the interesting, juicy stuff. The entire point of this was to learn CS every day, I added daily posts to keep myself accountable. I'll still be pushing a bullet-point-style log every day, and push interesting long form posts only when I have something interesting to write about.

Laying down ground work for a Bytecode Virtual Machine

Rahul Jha — Fri, 26 Mar 2021 04:13:35 +0000

Missed writing an entry yesterday, didn't miss coding though. Already done with laying down the foundation of clox, our Bytecode VM.

(I'm gonna be making this post very brief, because well, Bob already walks us through the entire code in the book -- https://craftinginterpreters.com/chunks-of-bytecode.html)

All we can do with clox right now is make a chunk and write to it. There is no front-end to the compiler, no interpretation of the code. Heck, we don't even have the full list of opcodes (each opcode is a unique byte which corresponds to a special instruction of our language, e.g., OP_RETURN for returning from a function.) yet.

Chunk. What chunk?

Consider a chunk as a sequence of codes, each a byte long. Now, these bytes might mean different things: either opcodes or pointers to the data those opcodes need. But, that's all a chunk is: A sequence of bytes.

How do we know which is which?

To interpret the meaning of these bytes, we need to iterate through the entire sequence, and match it against a list of values:

Say, the first value we encounter is 0x10. Let's assume that we had mapped it to OP_RETURN. (It is very unlikely for the first opcode to be OP_RETURN, but bear it for it makes the example easy).
Next byte in the chunk might correspond to OP_CONSTANT. Whenever we store a OP_CONSTANT, we also need to store the value this constant holds. By convention, the next byte holds the address of this value.

You can see a pattern here. Each opcode may have zero or more operands -- so our compiler can easily figure out which is which.

For now, all it does is exactly that. We hand-write a bunch of values in the chunk, like this, and let it "disassemble" it:

initChunk(&chunk);

int constant = addConstant(&chunk, 1.2);

// 122 is an arbitrary line number I passed.
writeChunk(&chunk, OP_CONSTANT, 122);
writeChunk(&chunk, constant, 122);

int constant2 = addConstant(&chunk, 456);
writeChunk(&chunk, OP_CONSTANT, 123);
writeChunk(&chunk, constant2, 123);

writeChunk(&chunk, OP_RETURN, 123);

disassembleChunk(&chunk, "Test Chunk");

Our disassembler outputs this:

== Test Chunk ==
0000  122 OP_CONSANT          0 '1.2'
0002  123 OP_CONSANT          1 '456'
0004    | OP_RETURN

Day 005: Blew off another day

Rahul Jha — Wed, 24 Mar 2021 00:13:57 +0000

Lots of busy work today. As the quarter is coming to end, I'm trying to wrap up everything at work. Only worked for 10 minutes or so before getting interrupted and going down another rabbit hole.

But, since you're here: do you know that you can use vars instead of calling the __dict__ method on an instance/class to get a dictionary of all the attributes? Very nifty.

Day 004: On Showing Up

Rahul Jha — Tue, 23 Mar 2021 00:07:20 +0000

This challenge is not about as much about learning or CS, as much it is about discipline and showing up. Showing up everyday, despite everything. The virtue Neil Gaiman talks about when we says:

Husband runs off with politican.
MAKE GOOD ART.

Leg crushed and then eaten by mutated Boa constrictor?
MAKE GOOD ART.

IRS on your trail?
MAKE GOOD ART.

Cat exploded?
MAKE GOOD ART.

Somebody on the internet thinks what you're doing is stupid, or evil, or has been done before?
MAKE GOOD ART.

Probably things will work out somehow, and eventually take the sting away, but that doesn't matter, DO ONLY WHAT YOU DO BEST.
MAKE GOOD ART.

So, I'm showing up here, everyday, to make good art. Of course, life gets in it's way, as it did today and I couldn't give a whole lot of time to learning, and towards making that compiler or writing about it. But, I decided to show up nevertheless!

Day 003: Crafting Interpreters

Rahul Jha — Sun, 21 Mar 2021 23:00:33 +0000

In the winter of 2019, protests erupted across my city when an anti-Muslim bill (now act) – CAA – was proposed in the Indian parliament. To stop the protestors from organizing, the city was cut off from the Internet. The shutdown (which would last for 8 days) didn't stop the protestors, but in a strange turn of events, it helped me finally pick up and start reading Bob Nystrom's Crafting Interpreters, wherein he walked us through the design and development of a language he called "Lox".

In the first half, we created "jlox", a Java implementation of the language. He in fact walked us through every line of Java code required to build the language from the ground up.

Partly, because I didn't want to do a copy-paste job with the code, but to be engaged with the material, and partly – em, mostly – because I don't know Java, I decided I would write it in Python. I got started, and one word at a time, I fell in love with it (and Bob and his writing). I got hard at work, borderline maniac, cranking at my computer screen almost every waking moment. And it took me exactly 8 days, and plox was finally there. It was very rewarding, seeing it alive and breathing.

The next half of the book discussed the implementation of the same language in C. It was called, you guessed it .. "clox". It wasn't just jlox written in c instead of Java, but it followed another execution model, the Bytecode virtual machine.

You see, jlox and plox were both "interpreters" for Lox. They worked by what's called "walking the tree", that is to say, they parse the user's program into a tree structure (which is very similar to ASTs I talk about in my other post) and then executed a block of code in Java/Python corresponding to each node in that tree. This made them heavily reliant on the machinery provided by the source language.

clox, on the other hand, would compile the program to bytecode (a series of instructions, many of which are one byte long, hence the name) and this bytecode would then be fed to a virtual machine which will execute those instructions and run the program.

I found this interesting and planned to finish the other half the next week, and that plan never got to C the light of the day.

But, I've scratched this itch to go, complete that part enough times for me to commit to it, and what better time than this 100-day challenge. This should hopefully also solve the problem of me spending way more time thinking about what to write for the challenge, instead of, you know, writing it.

Day 002: Why are hashes cached in dictionaries?

Rahul Jha — Sat, 20 Mar 2021 23:03:29 +0000

Taking a closer look at how key-value pairs are stored in Python dictionaries yesterday, I noticed that alongside storing the key+value, the hash of the key is also stored.

Why would that be?

It can't be to speed up the lookup, as we cannot get to the data (the tuple where the hash+key+value is stored) until we know it's address, and address can only be known by computing the hash first.

Why then?

Turns out that when resizing the addresses vector, the hash for all the keys in items needs to be recomputed. This is expensive to calculate, thus slowing down the resize operation. Caching the hash speeds things up:

def resize_to(n):
    new_addresses = [None] * n
    for index, entry in enumerate(entries):
         h = perturb = entry[0]  # No need to compute the hash.
         addr = h % n
         while new_addresses[i] is not None:
             addr = (5 * addr + 1 + perturb) % n
             perturb >>= 5
         new_addresses[addr] = index
    return new_addresses

Other than this, storing the hash has another benefit -- during lookup, there's an inequality test required, which ensures that we've arrived at the correct hash+key+value pair, and need not probe any further.

The lookup code from the earlier post:

def lookup(key):
    perturb = h = hash(key)
    address = addresses[h % n]

    while items[address][1] != key: # <- inequality test

        address = (5 * address + 1 + perturb) % n
        perturb >>= 5
    return items[address][2]

Comparing two objects for [in]equality can be an expensive operation. The solution here is to rely on the fact that "if two objects have unequal hashes, then the objects must be unequal as well", and use an equality checker like below:

def fast_is_equal(
    key, target_key, key_hash, target_key_hash
):
    if key is target_key: return True  # Identity implies equality
    if hash_key != hash_target_key: return False
    return key == hash_key

And then during the lookup:

# ...
    while not fast_is_equal(
        # reference: items[address] -> (hash, key, value)
        items[address][1], key, items[address][0], h
    ):
# ...

So, my initial guess was right in a way: it does indeed speeds up the lookup, just not in a way I thought it'd be.

How do Python Dictionaries work?

Rahul Jha — Sat, 20 Mar 2021 03:02:40 +0000

In this post, we'll dissect how a dictionary is represented in Python, and the hash-scheme it uses to achieve constant-time lookup.

{
    "name": "Rahul Jha",
    "alias": "RJ722",
    "music": "country",
    "cheat_diet": "pasta",
}

When we first create a dictionary, it internally maintains a list. This list is used to store "data" about the items in the dictionary, and comprises tuples in the following format:

(
   hash(key),
   key,
   value,
)

Each tuple referred to as a "row", represents a single key-value pair in the dictionary. When a new pair is added to the dictionary, it is appended to this list. This forms the "database" of the dictionary.

For our example above, the database will look like this:

[(7409878836864405608, 'name', 'Rahul Jha'),
 (2620441572017060194, 'alias', 'RJ722'),
 (205288631654089410, 'music', 'country'),
 (405166953458871902, 'cheat_diet', 'pasta')]

Along with creating the database, when a new dictionary is created, a chunk of memory is "blocked". This is used for addressing the keys, to say, which row in the database should be returned for a corresponding key. More on it later.

The size of this chunk determines the number of open addresses available. If all the open addresses are used up, a new memory chunk (usually double in size) is allocated and any values stored in these addresses are copied over. Generally, this is done when addresses are two-thirds (or 66%) full.

For the sake of this example, let's represent the "database" by a list items and the blocked memory chunk by a list addresses:

items = []
n = 8  # number of open addresses available
addresses = [None] * n

Addressing

To lookup a key in a dictionary, one need not search through the entire database. That way it won't be possible to maintain a constant lookup time.

The pairs are addressed instead. The address/position of each value in the database is computed based on the [hash] of the key.

To perform a lookup, one can simply hash the key, use it to compute the address, and read the value at the given address.

If the hashes for two or more keys collide, a technique called Open Address Multihashing helps resolve the address. Before understanding multihashing, let's first look at a simpler technique:

Linear Probing

If there's a collision for address i, the value, check i+1 address. If another value is stored at i+2 check for i+3, and so on until you find an empty slot:

def insert(key, value):
    h = hash(key)
    items.append((h, key, value))
    position = len(items) - 1 # the index of this row

    address = h % n
    while addresses[address] is not None:
        address = (address + 1) % n

    # Store the position at which the tuple can be found
    addresses[address] = position

Let's try it out:

insert("name", "Rahul Jha")
insert("alias", "RJ722")
insert("music", "country")
insert("cheat_diet", "pasta")

pprint(addresses)
#  [(7409878836864405608, 'name', 'Rahul Jha'),
#   (2620441572017060194, 'alias', 'RJ722'),
#   (205288631654089410, 'music', 'country'),
#   (405166953458871902, 'cheat_diet', 'pasta')]

pprint(items)
#  [0, None, 1, 2, None, None, 3, None]

Similarly, when looking up, one needs to probe adjacent addresses until the matching key is found:

def lookup(key):
    h = hash(key)
    address = addresses[h % n]
    while items[address][1] != key:
        address = (address + 1) % n
    return items[address][2]

print(lookup("name") ) # "Rahul Jha"

However, if a large number of addresses collide, linear probing can lead to a catastrophic linear pile-up, causing long chains of search and slowing down the lookup.

Note that the implementation above is incomplete: Removing keys can create "holes" which will break the chain, and probing would not be able to find keys that had a collision. The solution is to use mark the slot as DUMMY to serve as a placeholder. This technique is known as "Knuth – Algorithm D".

Open Address Multihashing

Rather than probing adjacent addresses, a new address is generated by re-hashing, based on both the prior hash value and the number of probes so far.

We add a pseudo-random number to the address probe – generated by a "simple linear-congruential random number generator": i = 5 * i + 1.

This, however, again scans addresses in a fixed order. To avoid this, the original hash is also added to the random number. This hash is then shifted 5 bits on each recurrence. This way the sequence depends (eventually) on every bit in the hash code and the pseudo-scrambling more aggressive:

def insert(key, value):
    h = hash(key)
    items.append((h, key, value))
    position = len(items) - 1 # the index of this row

    perturb = h
    address = h % n
    while addresses[address] is not None:
        address = (5 * address + 1 + perturb) % n
        perturb >>= 5

    # Store the position at which the tuple can be found
    addresses[address] = position

Carrying forward the same example as above, we can generate the addresses:

insert("name", "Rahul Jha")
insert("alias", "RJ722")
insert("music", "country")
insert("cheat_diet", "pasta")

pprint(items)
#  [(-6473745080427136004, 'name', 'Rahul Jha'),
#   (-1887375983119989115, 'alias', 'RJ722'),
#   (-4671665682772832904, 'music', 'country'),
#   (3463812311448012107, 'cheat_diet', 'pasta')]

pprint(addresses)
# [2, None, None, 3, 0, 1, None, None]

During lookup, we resolve collisions using the same recurrence pattern:

def lookup(key):
    perturb = h = hash(key)
    address = addresses[h % n]
    while items[address][1] != key:
        address = (5 * address + 1 + perturb) % n
        perturb >>= 5
    return items[address][2]

print(lookup("name"))  # "Rahul Jha"

Conclusion

Python uses two tables: one to store hash/key/value densely, and a separate, sparse table of indices that vectors the dense table.

It wasn't always this way. As Raymond Hettinger explains brilliantly in his talk "Modern Dictionaries" (which also provided the fodder for this post), dictionaries in Python 2.7 didn't have two tables. There was no table for addressing, only data -- A big sparse table. This lead to a lot of space being wasted in empty holes, and consequently, dictionaries being giant until Python3.6 (wherein this vector scheme was added by Hettinger).

Fun Question: Why do you think key hashes are also stored along with data?