Optimizing OOP with a Hash trick

Resources Community Resources
#32

This got a little out of control guys, let me tell you that I was studying a bit more about the Benchmark, and I noticed that there is a certain percentage that yields 0 nanoseconds in both cases, 50% for the trick and 67% for the hash.
Still, you could say that in a matter of stress, the condition trick would help a lot, I mean the use of it in time waits for example a repeat until or some specific gigantic load.

#33

Note that this is going to be my last post here, as I donā€™t like to clutter up topics and rather explain this here rather than PMS as other people may also get the chance to learn.

An array that isnā€™t seen as a dictionary by Lua internally is with no explicit keys:

local t =  {1, 2, 3}

Meanwhile an table (even if its an array) with explicit keys like this is seen as an dictionary by Lua as Lua isnā€™t smart, so it allocates about 4 slots in the hash part rather than the array part.

local t = {[1] = 1, [2] = 2, [3] = 3 }

This is mentioned by one of Luaā€™s creator them self, Robert. Iā€™ve linked down the article and you can just go to the topic where they discuss tables by scrolling down. Note that most of the performance tips are useless in Luau.

Quote from the article:

image
image1275Ɨ781 98 KB

Article: https://www.lua.org/gems/sample.pdf

If there is something in Luaā€™s internals that you could post, we wouldnā€™t need a roundabout discussion

Hereā€™s rather a summary on how tables are implemented (Lua 5.1):

image
image863Ɨ674 43.7 KB

. Lua tables are associative arrays and can be used like arrays or dictionaries. It doesnā€™t need to and canā€™t tell a difference because there is none. Theyā€™re all, in some way, AAs and thereā€™s a reason why you can still index arrays by their hash part, because they still use it.

Tables are infact associative arrays. However, arrays are different than dictionaries and this is where your confusion is coming from.

The primary difference stands out that the array part is just an array in C internally, whereas a hash part is just a hash table which is it self an array internally, that stores buckets (Buckets are the hash of a key stored in that array. Inside each bucket, consists of a linked list which holds nodes. Hereā€™s an example of what I mean.

local dict  = { 
    Bo = 1

}

print(dict.Bo) --> 1

Internally, dict.Bo is performed something similar to this:

  • The Bo key is first hashed (Note that the hash function will return the stored hash inside that string object, since strings are interned, their hash is precomputed as well), and a linked list is stored in a key (which is the hash of Bo string object) inside the array.

  • The linked list contains of nodes, and each node is defined like this: {next = ..., key = ..., value = ...}.

  • Lua will loop through the nodes in that linked list and check if the key we indexed is the same as node.key and if so, return its value via node.value. This for the most part, is a O(1) time complexity assuming there are NO hash collisions involved (Hash collisions will append new nodes to that specific linked list, increasing lookup time).

Looking at the source for how Lua internally gets a string keyā€™s value inside a dictionary:

image
image719Ɨ308 8.96 KB

First, the hash of the key is taken (It isnā€™t calculated but just returned) *n =hashstr(t, key). Lua gets the bucket and searches all the nodes in that bucket and checks if the nodeā€™s key member is the same as the key we indexed. If so, return the value of the node. If the key isnā€™t the same, then go to the next node via n = gnext(n). Finally return nil if it has searched all the nodes.

Meanwhile a search function for numbers:

image
image867Ɨ442 14 KB

5 Likes
#34

See? Now that wasnā€™t so hard! If this was your first post in response, we would have no off-topic debate on this thread and we could get on with our day without spending so many hours thinking about it!

Thank you for actually providing substance for your post this time around, so that we can actually have a chance to learn and correct potential misconceptions we may have been harbouring (assuming all this information is accurate - I myself, admittedly, am not well versed in Lua internals). This couldā€™ve gone much better.

+1 for the follow-up.

I did flag myself, but Iā€™m going to go ahead and delete some previous posts to avoid clutter in advance because I am clearly wrong and this is also a good moment for me to really practice what I preach and not speak on things I am not well versed on.

3 Likes