extra/benchmark/hashtables/hashtables.factor

   1 ! Copyright (C) 2009 Slava Pestov.
   2 ! See http://factorcode.org/license.txt for BSD license.
   3 USING: accessors assocs combinators grouping kernel math
   4 math.parser ranges sequences ;
   5 IN: benchmark.hashtables
   6
   7 MEMO: strings ( -- str )
   8     100 [0..b) 1 [ + ] accumulate* [ number>string ] map ;
   9
  10 :: add-delete-mix ( hash keys -- )
  11     keys [| k |
  12         0 k hash set-at
  13         k hash delete-at
  14     ] each
  15
  16     keys [
  17         0 swap hash set-at
  18     ] each
  19
  20     keys [
  21         hash delete-at
  22     ] each ;
  23
  24 :: store-lookup-mix ( hash keys -- )
  25     keys [
  26         0 swap hash set-at
  27     ] each
  28
  29     keys [
  30         hash at
  31     ] map drop
  32
  33     keys [
  34         hash [ 1 + ] assocs:change-at
  35     ] each ;
  36
  37 : string-mix ( hash -- )
  38     strings
  39     [ add-delete-mix ]
  40     [ store-lookup-mix ]
  41     2bi ;
  42
  43 TUPLE: collision value ;
  44
  45 M: collision hashcode* value>> hashcode* 15 bitand ;
  46
  47 : collision-mix ( hash -- )
  48     strings 30 head [ collision boa ] map
  49     [ add-delete-mix ]
  50     [ store-lookup-mix ]
  51     2bi ;
  52
  53 : small-mix ( hash -- )
  54     strings 10 group [
  55         [ add-delete-mix ]
  56         [ store-lookup-mix ]
  57         2bi
  58     ] with each ;
  59
  60 : hashtables-benchmark ( -- )
  61     H{ } clone
  62     10000 [
  63         dup {
  64             [ small-mix ]
  65             [ clear-assoc ]
  66             [ string-mix ]
  67             [ clear-assoc ]
  68             [ collision-mix ]
  69             [ clear-assoc ]
  70         } cleave
  71     ] times
  72     drop ;
  73
  74 MAIN: hashtables-benchmark