Reply To: Searching

As I read the problem description, N is in a set of 2^24 records of 12 members each, so that data clearly would not fit in cache. If N is in a linked list with scattered order, cache thrashing could be fierce, with near every new N hitting the full latency to RAM. ~5M cycles total estimate using 300 cycles/RAM access. The size of an individual member isn’t given, guessing 32bits. I’m also figuring 156 loads from cache (small register set) to perform a set of 144 comparisons between members of N.i and V.j in the SISD case. ~18M cycles total estimate. Still a log way from accounting for the time reported.