Searching 20 GB/sec: Systems Engineering Before Algorithms • Hacker News Board

Re: Searching 20 GB/sec: Systems Engineering Before Algorithms

#41

Post by jug6ernaut » Thu, May 08, 2014, 6:46 PM UTC

npsimons wrote: post #31

lifeisstillgood wrote: post #10

Earlier quoted context omitted.

I get the feeling this is more "era-defining" than that... What hit me was the "Processors are so fast now we can Brute force grep over 100GB in a second". We are entering a world where 20TB on a magnetic disk is viable, but randomly accessing that data could take months to extract. So how we store data on disks will become vitally important to how we use the data - not unlike tape drives of pre-1980s era where rewin…

What hit me was the "Processors are so fast now we can Brute force grep over 100GB in a second". Ironically, this may only be because grep uses very well tuned, not immediately straightforward algorithms. See in particular http://lists.freebsd.org/pipermail/freebsd-current/2010-Augu...

Awesome read, thanks for sharing! Almost worth a HN post in itself if you ask me.

Re: Searching 20 GB/sec: Systems Engineering Before Algorithms

#42

Post by phserr » Thu, May 08, 2014, 6:51 PM UTC

lifeisstillgood wrote: post #30

snewman wrote: post #17

Earlier quoted context omitted.

Indeed, in the not too distant future we expect to move to spinning disks, with the data arranged for streaming reads. Streaming off disk can be pretty fast. LZ4 compression is fast enough to give us another big boost without turning CPU into a bottleneck. But the big enabler will be spreading data across disks, so that in principle we can use every spindle we own in service of every nontrivial query. The fact that s…

Amazing how much work 'simple' is :-) I am reminded of John Carmack's comment on Oculus - he was amazed that the hardware had the power but the headsets performed badly - then he looked at the code and saw seas of abstractions on abstractions. Good luck stripping out the layers guys !

Has he written anything (or talked) about this experience or was it just a brief comment? I'd love to read it if he did.

Re: Searching 20 GB/sec: Systems Engineering Before Algorithms

#43

Post by barrkel » Thu, May 08, 2014, 7:05 PM UTC

justin66 wrote: post #36

vinkelhake wrote: post #23

I wrote a simple code search tool a number of years ago that had the ability to run arbitrary regex queries on a codebase, much like a recursive grep. I was working on a medium sized codebase and our primary platform was Windows. The problem with grep was that opening and scanning lots of small files apparently wasn't something that Windows was optimized for. If the file cache was cold, a simple search could turn int…

> The problem with grep was that opening and scanning lots of small files apparently wasn't something that Windows was optimized for. It's something hard disk drives were not optimized for.

He says hot cache - hdd is out of the loop, it should just be between the FS implementation and the cache implementation.

Re: Searching 20 GB/sec: Systems Engineering Before Algorithms

#44

Post by snewman » Thu, May 08, 2014, 7:12 PM UTC

retube wrote: post #12

In order to facilitate sub-word or wildcard searches can't you use a keycharacter index instead of a keyword index?

Yes, you can go down that road [0], and in some applications it's a good approach. However, it adds quite a bit of complexity, and the cost for creating and storing the index is substantial. For us, it doesn't pencil out to a win.

[0] http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.362...

Re: Searching 20 GB/sec: Systems Engineering Before Algorithms

#45

Post by j2kun » Thu, May 08, 2014, 7:16 PM UTC

jfasi wrote: post #15

j2kun wrote: post #13

They're not using any fancy algorithms...except when they implement a customized version of Boyer-Moore for better string searching in a critical section of their algorithm. Not to mention all the fancy algorithms optimizing their brute-force code underneath their immediately visible program. A better title would be, "How we determined when to use brute force."

Say what you will, but while Boyer-Moore can be tricky to implement, it's not exactly a fancy algorithm.

I think the real point is that they did a bona-fide tradeoff analysis and found that for their use case one algorithm was better than another. It's not about how fancy the algorithm is, that's just how great engineering works. It's only surprising if you don't consider "brute force" to be just as valid a tool as any other.

Re: Searching 20 GB/sec: Systems Engineering Before Algorithms

#46

Post by TheSOB888 » Thu, May 08, 2014, 7:28 PM UTC

innguest wrote: post #40

lifeisstillgood wrote: post #30

Earlier quoted context omitted.

Amazing how much work 'simple' is :-) I am reminded of John Carmack's comment on Oculus - he was amazed that the hardware had the power but the headsets performed badly - then he looked at the code and saw seas of abstractions on abstractions. Good luck stripping out the layers guys !

Interesting. That must be why C/C++ is always the go-to solution. Instead of thinking "too many abstractions are making this code slow, therefore let's get rid of the abstractions" I usually had rather pick a better language where abstractions have little or no penalty (Haskell, Scheme, etc).

Yeah, but the abstractions have a penalty on your mind.

Re: Searching 20 GB/sec: Systems Engineering Before Algorithms

#47

Post by TheSOB888 » Thu, May 08, 2014, 7:30 PM UTC

dragontamer wrote: post #29

I’d certainly seen this at Google, where they’re pretty good at that kind of thing. But at Scalyr, we settled on a much more brute-force approach: a linear scan through the log Art of Computer Programming mentions this methodology, and the importance of learning about it. There are entire sections of "Tape Algorithms" that maximize the "brute force linear scan" of tape drives, complete with diagrams on how a hypothet…

Why would you need a B-tree when you only append to the end of the logs?

Re: Searching 20 GB/sec: Systems Engineering Before Algorithms

#48

Post by npsimons » Thu, May 08, 2014, 7:34 PM UTC

jug6ernaut wrote: post #41

npsimons wrote: post #31

Earlier quoted context omitted.

What hit me was the "Processors are so fast now we can Brute force grep over 100GB in a second". Ironically, this may only be because grep uses very well tuned, not immediately straightforward algorithms. See in particular http://lists.freebsd.org/pipermail/freebsd-current/2010-Augu...

Awesome read, thanks for sharing! Almost worth a HN post in itself if you ask me.

I think it was posted a while back; it was an interesting enough article that it stuck in my head and I was able to find it pretty easily by googling "why is grep so fast?".

Ah, here it is:

https://news.ycombinator.com/item?id=2393587

And again!

https://news.ycombinator.com/item?id=6813937

And duplicate submissions are listed in those postings.