Link

Link

In the last week, I started with another implementation of sets, that uses Separate Chaining for collision-resolution. This was the second implementation, the first being with Linear Probing. This week, I completed this implementation, fixing bugs, and identifying some more in the existing dictionary implementation.

Set (Separate Chaining, continued) (#2198)

As described in the last post, this implementation uses one linked list per hash value to allow for more than one element having the same hash.

The earlier implementation had bugs that did not correct identify duplicates in the set. In addition, remove function was not actually removing elements due to incorrect assignment of variables. I fixed these and other issues, testing all of these in the integration tests.

To complete this, I benchmarked this implementation (updated gist here). It turns out that this new implementation is not significantly better than the Linear Probing one.

Reserve function (#2232)

I will work on this issue in the next week, as it affects existing benchmarks. This basically reserves space for a list at the start of an algorithm. Equivalent functions are available in C++ with the same name

In the past couple of weeks, an implementation of sets was completed. This week, I worked on benchmarking this. I also started work on another implementation, and progressed on some earlier dictionary issues.

Set Benchmark (GitHub Gist)

• This benchmarks the recent hash-set implementation that uses linear-probing for collision-resolution. We compare performance of this LPython data-structure with equivalent structures in Python (set) and C++ (unordered_set).
• Performance of functions set.add and set.remove is tested.
  • One way to do this is to simply insert and remove elements in order (say, from 1 to 1e7). However, this would not lead to collisions, as the set would be rehashed after reaching a size threshold (in our implementation, this is 0.6 of the capacity at any point).
  • To add some more complexity, we use random numbers. To generate pseudo-random numbers without adding major performance overheads, Lehmer random number generator  is used. In particular, the tests use Schrage's method to avoid 64-bit division. This is a straightforward algorithm that uses linear modular arithmetic to generate random numbers.
• As can be seen in the results, LPython outperforms both Python and C++. Surprisingly, C++ was slower than the equivalent Python code.
  • When dealing with integers, LPython is more than 4.5 times faster than C++, and more than 3.6 times faster than Python.
  • With strings, these gains are about 1.2 and 1.02, respectively.
• For C++, we also tested with custom hash functions, to mimic those used in our LPython implementation. This did not affect the results much.

​​​​​​​Set (Separate Chaining) (#2198)

• ​​​​​​​This is towards adding the separate-chaining collision-resolution technique. In contrast to linear probing, when collisions happen, we extend the pre-existing linked list of elements at that hash value. We already have it in dictionaries, but there are some issues in that implementation.
• I created all the basic functions, and will fix remaining bugs in the coming week.

​​​​​​​Dictionary (Keys and Values, continued) (#2023)

• ​​​​​​​I had implemented this in a previous week to work with the linear-probing implementation of dictionaries. Now, I extended these functions to also work with the separate-chaining implementation.
• We iterate over all the hash values, and if there is a corresponding linked list, we iterate over that, putting keys/values into a list, the latter returned at the end.

I worked on adding more functionality to sets, and fixing some existing issues.

- Sets (#2122, continued)

After the initial implementation was completed last week, I added functions to add and remove elements from sets.

• To add an element, its hash is computed, and we find an empty slot in the underlying array. This was done over the linear-probing implementation - if the spot corresponding to this hash is non-empty, a traversal is done starting from that position. Also, if the load factor crosses a threshold, a larger array is allocated, and all of the existing data is rehashed.
• To remove an element, the mask value is simply set to a special value (3). This is called a tombstone, marking deletion. At later insertions, this spot can be reused. However, care has to be taken while reading elements - this element must not be read.
• During the weekly meet with my mentor, we fixed an issue that wasn't reproducible for me locally, but was showing up on the workflows. This was occurring due to non-initialization of an interface member.

- Nested Dictionaries (branch nested_dict)

There is an existing issue (#1111) with the current dictionary implementation, which causes exceptions and segfaults when using nested dictionaries like dict[i32, dict[i32, i32]]. There was also an issue with assignment of empty dictionaries, i.e., d: dict[i32, dict[i32, i32]] = {}. This is now fixed (not merged yet). For the nesting, I found that the issue is with nested DictItem ASR nodes being present, which in turn try to read items that are not yet present. It seems that the solution is to have a DictInsert node at the innermost level, while keeping other nodes as is. I will try to fix this in the coming weeks.

- Set benchmarking

For the next week, I will also work on benchmarking our set implementation against C++ STL sets. We expect to perform (at least) at par with these, but if we find issues with some types (e.g. set of strings), we will also add the separate chaining implementation, as done for dictionaries.