Skip to content
Permalink

Comparing changes

Choose two branches to see what’s changed or to start a new pull request. If you need to, you can also or learn more about diff comparisons.

Open a pull request

Create a new pull request by comparing changes across two branches. If you need to, you can also . Learn more about diff comparisons here.
base repository: Ana06/ruby
Failed to load repositories. Confirm that selected base ref is valid, then try again.
Loading
base: master
Choose a base ref
...
head repository: Ana06/ruby
Failed to load repositories. Confirm that selected head ref is valid, then try again.
Loading
compare: tabulation_project
Choose a head ref
Checking mergeability… Don’t worry, you can still create the pull request.
  • 3 commits
  • 2 files changed
  • 1 contributor

Commits on May 9, 2020

  1. Enable Quadratic Probing

    Enable the already implemented Quadratic Probing algorithm. It was introduced
    in the following commit, alghough not enabled (it was not even compiled):
    7577515
    
    If we call `h(x)` to the hash function which maps `x` to a position in the
    hash, then the i-th probe position for `x` is given by the following function:
    `h(x,i) = h(x) + 1/2i + 1/2i^2`
    
    This produces the following probe sequence:
    `h(x), h(x) + 1, h(x) + 3, h(x) + 6, h(x) + 10, ...`
    In this sequence the increase values are triangular numbers, making it
    efficient to implement.
    
    Quadratic Probing may perform better than the current enabled implementation
    with Tabulation Hashing, which I plan to implement next.
    Ana06 committed May 9, 2020
    Configuration menu
    Copy the full SHA
    5a3fd57 View commit details
    Browse the repository at this point in the history
  2. Implement Linear Probing

    Implement and enable Linear Probing. Keep the other two implementations under
    the macro `PROBING`.
    
    If we call `h(x)` to the hash function which maps `x` to a position in the
    hash, then the i-th probe position for `x` is given by the following function:
    `h(x,i) = h(x) + i`
    In other words, if a collision occurs, we try the next hash cell until we find
    one empty.
    
    Linear Probing may perform better than the two other implementations with
    Tabulation Hashing, which I plan to implement next.
    Ana06 committed May 9, 2020
    Configuration menu
    Copy the full SHA
    11967eb View commit details
    Browse the repository at this point in the history

Commits on May 10, 2020

  1. Implement Simple Tabulation

    In spite of its simple implementation, Simple Tabulation provides many desired
    guarantees, such as linear probing. Reference:
        Thorup, Mikkel. "Fast and powerful hashing using tabulation."
        Communications of the ACM 60.7 (2017): 94-101.
        https://dl.acm.org/doi/abs/10.1145/3068772
    
    This is just a proof of concept to figure out if Simple Tabulation could
    improve the performance of the current Ruby Hashing implementation. The code is
    not in the correct place and it is only implemented for 64 bits and for the
    general case (excluding strings, numbers and symbols). But this is enough to
    prove the potential of Simple Tabulation. Below are the results got executing
    the following code:
    https://gist.github.com/Ana06/cc6f3a737ad16548996a22718de8b01b
    
    Time to add 600000 objects to an empty hash 100 times:
        - master (without Simple Tabulation): 29.68
        - master with Linear Probing (without Simple Tabulation): 99.76
        - master with Quadratic Probing (without Simple Tabulation): 29.97
        - master with Simple Tabulation: 15.76
        - master with Linear Probing and Simple Tabulation: 24.23
        - master with Quadratic Probing and Simple Tabulation: 13.92
    
    The results are in seconds. `master` refers to ruby 2.8.0dev
    (2020-05-07T16:22:38Z master 7ded8fd) [x86_64-linux].
    I tried with 8 x Intel i5-8265U at 1.60 GHz.
    Ana06 committed May 10, 2020
    Configuration menu
    Copy the full SHA
    dbf917a View commit details
    Browse the repository at this point in the history
Loading