Re: Why Seq search is faster than Table search

[treeform]

I love performance puzzles like this!

Answer: Turns it it just optimizes the for loops away!

Timings i get with the code provided:
    
    
    List: (seconds: 0, nanosecond: 9180)
    Table: (seconds: 0, nanosecond: 2794545)
    
    
    Run

Really strange!

Added dummy counter so that for loops don't get optimized out. In fact, program 
ran so slow I had to change the counter to 1000:
    
    
    import std/monotimes
    import tables
    import random
    var myTable = initTable[int, int]()
    var myList: seq[int]
    
    for i in 0 .. 1_000:
        myTable[i] = i
        myList.add(i)
    
    myList.shuffle()
    
    var start = getMonoTime()
    var dummyCounter = 0
    for i in 0 ..< 1_000:
        if myList.contains(i):
          inc dummyCounter
    echo("List: ", getMonoTime() - start)
    
    start = getMonoTime()
    for i in 0 ..< 1_000:
        if myTable.hasKey(i):
          inc dummyCounter
    echo("Table: ", getMonoTime() - start)
    echo dummyCounter
    
    
    Run
    
    
    List: (seconds: 0, nanosecond: 142290)
    Table: (seconds: 0, nanosecond: 3060)
    
    
    Run

Tables are soo soo much faster!