An interesting data structure with search time O(sqrt n)

#1

Post by z3phyr » Mon, Nov 30, 2015, 10:18 PM UTC

An interesting data structure with search time O(sqrt n)
forum.dlang.org

Re: An interesting data structure with search time O(sqrt n)

#2

Post by jegutman » Mon, Nov 30, 2015, 10:50 PM UTC

Even just that question: "Why?" and the corresponding answer are worth a read.

Re: An interesting data structure with search time O(sqrt n)

#3

Post by gamesbrainiac » Mon, Nov 30, 2015, 10:53 PM UTC

This is a very interesting discussion, but I'd like to ask a question about this in particular:

> The short of it is, arrays are king. No two ways about it - following pointers is a losing strategy when there's an alternative.

Why is following pointers a losing strategy? If you have a contiguous array (a vector), then the pre-fetcher can do its magic and give you a psuedo-cache level. (I may be wrong about this assumption).

Re: An interesting data structure with search time O(sqrt n)

#4

Post by marvy » Mon, Nov 30, 2015, 10:58 PM UTC

gamesbrainiac wrote: post #3

This is a very interesting discussion, but I'd like to ask a question about this in particular: > The short of it is, arrays are king. No two ways about it - following pointers is a losing strategy when there's an alternative. Why is following pointers a losing strategy? If you have a contiguous array (a vector), then the pre-fetcher can do its magic and give you a psuedo-cache level. (I may be wrong about this assum…

You just (partially) answered your own question. Imagine something like a binary search tree. With all the pointer chasing you'll be doing, the poor pre-fetcher doesn't stand a chance.

Re: An interesting data structure with search time O(sqrt n)

#5

Post by slowernet » Mon, Nov 30, 2015, 10:58 PM UTC

gamesbrainiac wrote: post #3

This is a very interesting discussion, but I'd like to ask a question about this in particular: > The short of it is, arrays are king. No two ways about it - following pointers is a losing strategy when there's an alternative. Why is following pointers a losing strategy? If you have a contiguous array (a vector), then the pre-fetcher can do its magic and give you a psuedo-cache level. (I may be wrong about this assum…

I'm missing how your first sentence is connected to your second (are you suggesting a contiguous array of pointers?) but I believe the generalized disadvantage of pointers is poor locality of memory access, cache misses, etc.

Re: An interesting data structure with search time O(sqrt n)

#6

Post by tux3 » Mon, Nov 30, 2015, 11:07 PM UTC

gamesbrainiac wrote: post #3

This is a very interesting discussion, but I'd like to ask a question about this in particular: > The short of it is, arrays are king. No two ways about it - following pointers is a losing strategy when there's an alternative. Why is following pointers a losing strategy? If you have a contiguous array (a vector), then the pre-fetcher can do its magic and give you a psuedo-cache level. (I may be wrong about this assum…

The prefetcher works only if it can predict what you're going to access next. Chasing pointers means essentially jumping to random addresses in a given memory region. That's pretty much the worst situation from a caching point of view, what the prefetcher loves is linear traversal.

Of course things become more complicated when you start having larger amounts of data, and you want to skip over most of it, but still keep the cache happy.

Re: An interesting data structure with search time O(sqrt n)

#7

Post by mjevans » Mon, Nov 30, 2015, 11:11 PM UTC

The context of the proposed data structure is more important for evaluating how effective it is at maximizing performance.

This context includes not only the characteristics of the (typical) systems using the data layout, but also the typical use of that structure (read heavy, write heavy, some mix). The cost of memory is also an issue. For a typical end user program the bottleneck is almost always going to be the user. For larger scale programs or more performance intensive areas of a program (E.G. graphics languages or other large data operations) different tradeoffs should be evaluated.

Re: An interesting data structure with search time O(sqrt n)

#8

Post by Einherji » Mon, Nov 30, 2015, 11:12 PM UTC

jegutman wrote: post #2

Even just that question: "Why?" and the corresponding answer are worth a read.

Agreed. I love that this came from noticing a "gap" and coming up with something to fill the hole. I wish I thought like this more often!

Re: An interesting data structure with search time O(sqrt n)

#9

Post by biot » Mon, Nov 30, 2015, 11:14 PM UTC

I'm not sure I'm able to visualize this correctly. Let's say we have an array of strings containing the top 20 movies from Rotten Tomatoes:

  The Wizard of Oz
  The Third Man
  Citizen Kane
  All About Eve
  Das Cabinet des Dr. Caligari. (The Cabinet of Dr. Caligari)
  Modern Times
  A Hard Day's Night
  The Godfather
  E.T. The Extra-Terrestrial
  Metropolis
  It Happened One Night
  Singin' in the Rain
  Laura
  The Adventures of Robin Hood
  Inside Out
  Repulsion
  Boyhood
  North by Northwest
  King Kong
  Snow White and the Seven Dwarfs

What would this data structure look like?

Re: An interesting data structure with search time O(sqrt n)

#10

Post by davidhariri » Mon, Nov 30, 2015, 11:17 PM UTC

From what I understand, this is how Medium organizes the fast retrieval and editing of their rich text. You might want to read this for more information: https://medium.com/medium-eng/why-contenteditable-is-terribl...

I may have missed something, though :-|