Function call overhead reduction Hash on the top of RB-Tree implementation of map

(I slept badly last night because these thoughts came into my mind just before sleeping. Luckily these thoughts seem well to be useful. Sometimes I found myself repeating some thoughts almost subconsciously, probably it's because I was subconsciously afraid I would forget those thoughts or they were not concrete enough, writing them down should relieve this:-))

1 Function call overhead reduction

Top

Dao supports function overloading, which imposes a significant overhead to function call, because when a function is called, the parameters have to be checked against the parameter types of a list of overloaded functions. Such checking is time consuming.

One possible way to solve this is to encode function prototypes into string, and encode the calling parameter types into string as well, and then use such strings for function lookup. But it seems to me than, to do this efficiently and safely, it requires a more strict typing system. Or maybe some languages were doing in the same way as I am going to describe.

In the method I am going to describe, it is still necessary to encode the calling parameter types into a signature string, but not the function prototypes. The key idea here is caching -- caching the type checking results for the future function calls.

From time to time, I had thought about caching as the right way to go, but it was not obvious how. Now it seems it can actually be done fairly simply. The idea is related to (possibly inspired by) that idea behind the planned feature for binding interface as prototype I posted yesterday.

The idea is based on two round hashing (one round should also work, but less efficient):

1. a hash to associate signature strings to representative objects (address);
2. a hash to associate the combinations of representative object (address) and function object (address) to cached type checking results.

The first has could be global to a process, and the second could be local to each set of overloaded functions. When a function is called, encode the calling parameter types on the fly to a signature string, then use this signature to lookup if there is cached type checking results. If there is, use the cached results to select the right function to call. Otherwise, perform detailed type checking between the calling types and the overloaded functions, and cache the results in the hash tables.

2 Hash on the top of RB-Tree implementation of map

Top

When I was thinking about using hash to reduce function call overhead, somehow it came into my mind that I can implement a hash type on the top of the existing rb-tree implementation of map. Certainly it will not be the best way to implement hash table, but it will take a minimum amount of effort by using the existing code base.

The idea is also very simple: hash the keys to rb-tree nodes, and store some (or all) of the nodes in an extra array. For key lookup, compute the hash value of the query key and find the corresponding tree node in the array, if the node has key equals to the query key, return the value hold by the node (O(1)); otherwise, search the branches starting from that tree node (O(1)~O(log(n))). For this, the key comparison between keys for the rb-tree must first compare their hashed values and then their values.

For key insertion, insert it to the rb-tree as usual (sorted first by key hash values then key values). Then check if there is a node in the extra node array has the same key has value, if there is, check which one is higher (closer to the root) in the tree, and set that one in the node array. In the best case it will take O(1) time, when the new node and the existing node in the array are directly linked in the tree. The worst case happens, when the array need to be increased, which will take O(n).

Similarly, with extra steps for updating the node array, key deletion can be done in O(1) to O(n) time.

Time complexity:

Operation	Best	Worst
Lookup	O(1)	O(log(n))
Insertion	O(1)	O(n)
Deletion	O(1)	O(n)

Once this is implemented, an extra syntax construct can be added to Dao, like: Which will also create an associative array, where the keys are unordered. Whereas, associative array created by, will have ordered keys. (extra methods will be added to map type to convert from one to the other)

There has been requests to use : instead of => in constructing associative array, mainly because that's what Python dictionary type uses. The above solution will not only solve this issue, it will actually bring that data type closer to the Python dictionary:-)