?

Log in

Erlang Hash Table - Michael Truog
okeuday
Erlang Hash Table
I created hasht, a simple hash table implementation that performs quick lookups. Setting the structure is quite slow because it always modifies a single large tuple. However, with a more tiered approach, the storage speed might increase. The hasht lookup time for strings is similar to the trie data structure, but is slower for smaller N. The hasht lookup time for integers is similar to ETS (unless the ETS table is accessed with greater than ~10 processes concurrently with read concurrency optimizations set on the table), but the process dictionary and tuple are both quicker for integer lookups. The benchmark results are from Linux version 2.6.32-21, Ubuntu 10.04 with an Intel(R) Core(TM)2 CPU T5600 @ 1.83GHz and non-HiPE Erlang R14B01:
TEST string_key
N == 1000 (10 runs)
              aadict get:      828.6 µs (  1.5), set:     2226.0 µs (  1.4)
                dict get:      940.9 µs (  1.7), set:     3184.6 µs (  2.0)
           ets (set) get:      828.5 µs (  1.5), set:     1586.9 µs (  1.0)
       ets x10 (set) get:     1030.8 µs (  1.8)
            gb_trees get:      897.6 µs (  1.6), set:     2786.5 µs (  1.8)
               hasht get:     1392.5 µs (  2.5), set:     9815.1 µs (  6.2)
  process dictionary get:      566.3 µs (  1.0), set:     1618.2 µs (  1.0)
              rbdict get:      817.3 µs (  1.4), set:     1806.3 µs (  1.1)
                trie get:      650.9 µs (  1.1), set:     2466.6 µs (  1.6)
N == 10000 (10 runs)
              aadict get:    21320.8 µs (  2.6), set:    45882.9 µs (  2.1)
                dict get:    17345.4 µs (  2.1), set:    59625.4 µs (  2.7)
           ets (set) get:    16985.1 µs (  2.0), set:    22305.2 µs (  1.0)
       ets x10 (set) get:    21002.8 µs (  2.5)
            gb_trees get:    23835.2 µs (  2.9), set:    47572.9 µs (  2.1)
               hasht get:    13345.9 µs (  1.6), set:  1030469.0 µs ( 46.2)
  process dictionary get:    12837.2 µs (  1.5), set:    25609.6 µs (  1.1)
              rbdict get:    21680.3 µs (  2.6), set:    42978.7 µs (  1.9)
                trie get:     8351.5 µs (  1.0), set:    35003.4 µs (  1.6)
N == 50000 (10 runs)
              aadict get:   179311.1 µs (  2.9), set:   326961.5 µs (  2.4)
                dict get:   111803.5 µs (  1.8), set:   615110.2 µs (  4.6)
           ets (set) get:    91941.2 µs (  1.5), set:   135026.9 µs (  1.0)
       ets x10 (set) get:   107469.8 µs (  1.7)
            gb_trees get:   195219.1 µs (  3.1), set:   358408.6 µs (  2.7)
               hasht get:    66421.6 µs (  1.1), set: 27200459.7 µs (201.4)
  process dictionary get:    62683.4 µs (  1.0), set:   141821.2 µs (  1.1)
              rbdict get:   182102.3 µs (  2.9), set:   294744.7 µs (  2.2)
                trie get:    71213.7 µs (  1.1), set:   357100.4 µs (  2.6)
TEST integer_key
N == 1000 (10 runs)
              aadict get:      482.5 µs (  5.6), set:     1917.5 µs ( 13.1)
     array (dynamic) get:      393.3 µs (  4.5), set:      721.6 µs (  4.9)
       array (fixed) get:      393.7 µs (  4.6), set:     1080.2 µs (  7.4)
                dict get:      447.6 µs (  5.2), set:     2010.5 µs ( 13.7)
           ets (set) get:      333.3 µs (  3.9), set:      748.7 µs (  5.1)
       ets x10 (set) get:      203.2 µs (  2.3)
            gb_trees get:      476.2 µs (  5.5), set:     4339.8 µs ( 29.6)
               hasht get:      358.1 µs (  4.1), set:     7134.3 µs ( 48.7)
  process dictionary get:      133.6 µs (  1.5), set:      146.5 µs (  1.0)
              rbdict get:      478.0 µs (  5.5), set:     2027.6 µs ( 13.8)
               tuple get:       86.5 µs (  1.0), set:     6903.4 µs ( 47.1)
N == 10000 (10 runs)
              aadict get:     6670.9 µs (  8.3), set:    24593.4 µs ( 14.3)
     array (dynamic) get:     4968.5 µs (  6.1), set:     9641.3 µs (  5.6)
       array (fixed) get:     5057.3 µs (  6.3), set:     8929.1 µs (  5.2)
                dict get:     4857.0 µs (  6.0), set:    29415.4 µs ( 17.1)
           ets (set) get:     3695.3 µs (  4.6), set:     8625.1 µs (  5.0)
       ets x10 (set) get:     1896.0 µs (  2.3)
            gb_trees get:     6234.5 µs (  7.7), set:    72117.2 µs ( 42.0)
               hasht get:     2386.1 µs (  3.0), set:  1042563.7 µs (607.4)
  process dictionary get:     1317.5 µs (  1.6), set:     1716.3 µs (  1.0)
              rbdict get:     6772.1 µs (  8.4), set:    25672.9 µs ( 15.0)
               tuple get:      808.1 µs (  1.0), set:   613975.0 µs (357.7)
N == 50000 (10 runs)
              aadict get:    36984.9 µs (  9.2), set:   166405.2 µs ( 16.8)
     array (dynamic) get:    30181.9 µs (  7.5), set:    58707.0 µs (  5.9)
       array (fixed) get:    30171.7 µs (  7.5), set:    60833.8 µs (  6.2)
                dict get:    27988.1 µs (  7.0), set:   408414.5 µs ( 41.3)
           ets (set) get:    25076.6 µs (  6.3), set:    50396.9 µs (  5.1)
       ets x10 (set) get:    12081.4 µs (  3.0)
            gb_trees get:    35874.3 µs (  9.0), set:   405197.7 µs ( 41.0)
               hasht get:    13516.8 µs (  3.4), set: 26560861.7 µs (*****)
  process dictionary get:     6687.2 µs (  1.7), set:     9888.3 µs (  1.0)
              rbdict get:    36388.4 µs (  9.1), set:   152543.6 µs ( 15.4)
               tuple get:     4002.1 µs (  1.0), set: 18081650.6 µs (*****)
Leave a comment