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

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

#31

Post by npsimons » Thu, May 08, 2014, 5:26 PM UTC

lifeisstillgood wrote: post #10

patio11 wrote: post #3

This comes up in my work modestly frequently, generally with a slightly different scenario for the tradeoff between "complicated and considered" versus "cheap and dirty but gets the job done." e.g. We could spend 3 weeks using feature vectors and backtesting against prior data to figure out what signals accounts which are likely to churn send (for the purpose of proactively identifying them and attempting to derisk t…

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...

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

#32

Post by ddorian43 » Thu, May 08, 2014, 5:31 PM UTC

Look at their pricing. The best gb/$ public plan, is 500$ month for (worst case scenario) 300gb of data at all time.

With that price, you can keep most of the data in memory-ssd and don't care to use fancy-algorithm.

But what if the pricing was 10x lower ?

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

#33

Post by nicholassmith » Thu, May 08, 2014, 5:35 PM UTC

patio11 wrote: post #3

This comes up in my work modestly frequently, generally with a slightly different scenario for the tradeoff between "complicated and considered" versus "cheap and dirty but gets the job done." e.g. We could spend 3 weeks using feature vectors and backtesting against prior data to figure out what signals accounts which are likely to churn send (for the purpose of proactively identifying them and attempting to derisk t…

I will always pick the cheap and dirty option until the project is at a stage where you have a lot of breathing room. Simple code trumps fancy code in reality where you don't have a large team, and you don't have a lot of time and you need something that works even if it's only half as efficient a solution.

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

#34

Post by [deleted] » Thu, May 08, 2014, 5:37 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...

[deleted]

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

#35

Post by victor106 » Thu, May 08, 2014, 5:51 PM UTC

snewman wrote: post #18

jfasi wrote: post #15

Earlier quoted context omitted.

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

Exactly; "fancy" is relative. It's a bit tricky, but it's nothing like the complexity of maintaining and using a keyword index. The reference implementation given in the article we linked to is thirty-odd lines of code. What we're using in practice is somewhat larger, in part because Java is more verbose for this kind of thing, but still reasonable. (If there's interest, we'd be happy to post the code.)

Would love to look at your code...

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

#36

Post by justin66 » Thu, May 08, 2014, 5:51 PM UTC

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.

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

#37

Post by jcampbell1 » Thu, May 08, 2014, 5:57 PM UTC

ddorian43 wrote: post #32

Look at their pricing. The best gb/$ public plan, is 500$ month for (worst case scenario) 300gb of data at all time. With that price, you can keep most of the data in memory-ssd and don't care to use fancy-algorithm. But what if the pricing was 10x lower ?

300 GB of ram, is going to cost ~ $3000/month.

Reading 300GB from an SSD is going to be way too slow. It will take minutes per search. In a simple test on linode, the SSD seems to read at about 1GB/s.

Their pricing seems like a bargain to me.

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

#38

Post by up_and_up » Thu, May 08, 2014, 6:05 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...

> The key to making programs fast is to make them do practically nothing.

Great quote from that referenced post.

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

#39

Post by suyash » Thu, May 08, 2014, 6:37 PM UTC

@Author: First of all simple code and fancy algorithms are not opposites. Actually a very simple code (elegantly and concisely written) can be have a really fast performance on the order of O(1). What you're suggesting is a very naive way of looking at the problem.

Secondly, you need to understand Algorithm analysis in little more detail. If you look at run time analysis of your brute force algorithm, you can determine, of it grows in linear time, logarithmic, exponential etc and how to improve upon the core algorithm. Anyone can add more machines, more memory, faster processor which will obviously help in improving performance but in comparison to order of growth of 'n' all of that pales in the background.

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

#40

Post by innguest » Thu, May 08, 2014, 6:41 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 !

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).