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

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

#71

Post by lucian1900 » Fri, May 09, 2014, 9:49 AM UTC

to3m wrote: post #62

vinkelhake wrote: post #52

Earlier quoted context omitted.

Windows is (or at least was) a dog when it comes to this even if the files are in the cache. Like barrkel said, the number I quoted was for the case when the OS doesn't hit the drive.

Random rant time! You have to code for Windows just so. Dear POSIX people in general, there is more to cross platform coding than being able to build it with cygwin. Every grep I've used on Windows handles wildcards, so it must be doing the expansion itself. The right way to do this sort of thing on Windows is to call FindFirstFile/FindNextFile, which is a cross between readdir and stat in that each call returns not…

Perhaps it'd be less bad if Windows wasn't so gratuitously different.

On a more serious note, there's a pretty large gulf between the Windows and Unix development worlds. Try getting a game developer to use curl ...

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

#72

Post by mercurial » Fri, May 09, 2014, 9:59 AM UTC

TheSOB888 wrote: post #46

innguest wrote: post #40

Earlier quoted context omitted.

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.

They do? In my experience, lack of abstraction (often due to not analyzing the issue at hand thoroughly) results in non-abstract, verbose, hard to understand and refactor code. It's the difference between, say, building an SQL query by appending strings to a buffer (move one line and everything blows up) and building a model of your query (projection, etc...). Sure, the abstraction means more code, but it's much more easier to manipulate and considerably less risk-prone. It won't be faster than doing it the other way, but it won't be necessarily measurably slower.

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

#73

Post by dekhn » Fri, May 09, 2014, 12:19 PM UTC

hvidgaard wrote: post #68

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…

When analyzing big data algorithms, the amount of computation by the CPU is often irrelevant. It's ignored. What matters is disk reads and disk access patterns. If you can make a scanning algorithm that start at byte 0, and reads everything once in a sequential manner, you can make O(n^4) computation with it. The CPU will be long finished with the inefficient computation by the time the next set of data is retrieved…

I don't think I've ever heard anybody claim that streaming algorithms permit O(n4) computation. That seems implausible. Most streaming algorithms are linear, or sublinear. I'm not sure what you meant by O or n or 4, however.

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

#74

Post by raphaelj » Fri, May 09, 2014, 12:55 PM UTC

dekhn wrote: post #73

hvidgaard wrote: post #68

Earlier quoted context omitted.

When analyzing big data algorithms, the amount of computation by the CPU is often irrelevant. It's ignored. What matters is disk reads and disk access patterns. If you can make a scanning algorithm that start at byte 0, and reads everything once in a sequential manner, you can make O(n^4) computation with it. The CPU will be long finished with the inefficient computation by the time the next set of data is retrieved…

I don't think I've ever heard anybody claim that streaming algorithms permit O(n 4) computation. That seems implausible. Most streaming algorithms are linear, or sublinear. I'm not sure what you meant by O or n or 4, however.

Indeed, there will always be an instant, given that "n" is increasing toward infinity, when the computation time will take over the streaming time.

Systems complexity are always bounded by their algorithm having the greatest complexity. As streaming is linear, there will always be a value of "n" after which the computation will take over, even with a very quasi-linear complexity (even an O(n^1.00000001) computation will be slower than the streaming for very very large values of n).

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

#75

Post by herf » Fri, May 09, 2014, 2:50 PM UTC

Wilya wrote: post #55

jcampbell1 wrote: post #37

Earlier quoted context omitted.

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.

300GB of ram might cost $3000/month on AWS. There are a few dedicated server providers that offer 384GB or even 512GB configs for less than 1000$/month.

lz4 typically compresses logs 6:1 (note: the "high compression" mode allows fast searching.)

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

#76

Post by herf » Fri, May 09, 2014, 2:52 PM UTC

to3m wrote: post #62

vinkelhake wrote: post #52

Earlier quoted context omitted.

Windows is (or at least was) a dog when it comes to this even if the files are in the cache. Like barrkel said, the number I quoted was for the case when the OS doesn't hit the drive.

Random rant time! You have to code for Windows just so. Dear POSIX people in general, there is more to cross platform coding than being able to build it with cygwin. Every grep I've used on Windows handles wildcards, so it must be doing the expansion itself. The right way to do this sort of thing on Windows is to call FindFirstFile/FindNextFile, which is a cross between readdir and stat in that each call returns not…

Yes don't call GetFileAttributes (which your POSIX layer does to emulate grep) - especially over a network (samba) connection.

But the original point is OPEN is expensive, which it really is, especially over a network connection.

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

#77

Post by serbrech » Sun, May 11, 2014, 8:51 AM UTC

Why not building on top of existing full text index/search engines? Why would I choose this over something like Kibana (http://rashidkpc.github.io/Kibana/) that provides me with all this and more, is built on top of existing capable, scalable open source products, and is itself free and open source?

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

#78

Post by waps » Sun, May 11, 2014, 5:02 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).

Euhm abstractions in Haskell carry lots of penalties. Haskell is generally a language that only makes sense if you buy the "sufficiently smart compiler" argument. Haskell's abstractions shouldn't carry a penalty, because the compiler compiles them out when it recognizes them.

That's cute but while it's impressive what it recognizes, it's generally still stupid, and it will get beaten by bad programmers (especially by bad programmers. Becoming good at Haskell means, amongst other things, learning what the compiler will screw up).

Scheme, likewise, doesn't have free abstractions. Unless you mean macros, but those are not really free either imho.

There's one high-level language in wide use that has "free" abstractions, or at least, costs as low as possible, and that's C++.

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

#79

Post by hvidgaard » Mon, May 12, 2014, 8:18 AM UTC

raphaelj wrote: post #74

dekhn wrote: post #73

Earlier quoted context omitted.

I don't think I've ever heard anybody claim that streaming algorithms permit O(n 4) computation. That seems implausible. Most streaming algorithms are linear, or sublinear. I'm not sure what you meant by O or n or 4, however.

Indeed, there will always be an instant, given that "n" is increasing toward infinity, when the computation time will take over the streaming time. Systems complexity are always bounded by their algorithm having the greatest complexity. As streaming is linear, there will always be a value of "n" after which the computation will take over, even with a very quasi-linear complexity (even an O(n^1.00000001) computation w…

I should have mentioned that it implies that you can work on sufficiently small values of n, usually measured in how many cache lines it takes up. Saying that "there will always be a value of "n" after which the computation will take over" is, while true, completely theoretical. Not that it have its uses, but I have yet to see a IO heavy process being limited by the CPU. If it's streaming, it's usually also quite simple to process, and if it's random access the CPU is doing something else most of the time.

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

#80

Post by hvidgaard » Mon, May 12, 2014, 8:30 AM UTC

dekhn wrote: post #73

hvidgaard wrote: post #68

Earlier quoted context omitted.

When analyzing big data algorithms, the amount of computation by the CPU is often irrelevant. It's ignored. What matters is disk reads and disk access patterns. If you can make a scanning algorithm that start at byte 0, and reads everything once in a sequential manner, you can make O(n^4) computation with it. The CPU will be long finished with the inefficient computation by the time the next set of data is retrieved…

I don't think I've ever heard anybody claim that streaming algorithms permit O(n 4) computation. That seems implausible. Most streaming algorithms are linear, or sublinear. I'm not sure what you meant by O or n or 4, however.

I wrote it in a hurry. O(n^4) is only for the size of the current chunk of data being operated on, usually measured in cache lines. I guess it should have been m, as n is usually used for the total input size. It's not unusual to see O(m^c * log n) algorithms or even O(m^c * log log n) if you can use vEB search structure, where m is the number of cache lines the algorithm works on, c is an algorithm specific constant, and n is the total input size.