Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Searching 20 GB/sec: Systems Engineering Before Algorithms

blog.scalyr.com

Post reply on HN
Print view View original

81–87 of 87 posts

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

#81

Post by dekhn »

hvidgaard wrote: post #80
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.

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…

Ah, OK. So you meant space overhead in practical terms

I would think that a greater than constant time overhead would not be compatible with a real time streaming operation. just a guess, though.

Thanks for mentioning http://en.wikipedia.org/wiki/Van_Emde_Boas_tree as I hadn't heard of that. The last paragraph on the page gives some nice pointers (use a trie or randomized hash table).

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

#82

Post by dekhn »

hvidgaard wrote: post #79
raphaelj wrote: post #74

Earlier quoted context omitted.

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 sim…

I have a hard time working between statements that say "O(n4) growth" and then reference cache lines- to me, cache lines are just faster RAM.

http://lemire.me/blog/archives/2013/07/11/big-o-notation-and...

I always think of big-O in terms of algorithm analysis, while real-world performance is more a function of operation costs/memory costs. Its use in the latter is more colloquial but I get what you mean now.

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

#83

Post by sitkack »

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.

HDD don't care about opening files. If the FS supported the same operations, I could send grep directly to the block level and have it scan contiguous lists of blocks that cover files I care about. You will get false positives for the overscan (potentially), but you will also achieve the raw rate of the disk (150MB/s for spinning and 500MB/s for solid sate).

So in effect, these big data serialization systems are attempting to lift the file system into userland so they can make just that optimization.

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

#84

Post by shantanugoel »

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…

Aside to the discussion, can you point out a link to the changes you did? I'd like to get silver searcher faster as well on windows.

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

#85

Post by hvidgaard »

dekhn wrote: post #82
hvidgaard wrote: post #79

Earlier quoted context omitted.

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 sim…

I have a hard time working between statements that say "O(n 4) growth" and then reference cache lines- to me, cache lines are just faster RAM. http://lemire.me/blog/archives/2013/07/11/big-o-notation-and... I always think of big-O in terms of algorithm analysis, while real-world performance is more a function of operation costs/memory costs. Its use in the latter is more colloquial but I get what you mean now.

As long as you do not have algorithmic dependence within the data in a cache line, you can regard calculation on that data as a constant that is dependent on the size of the data in the cache line. Even more so if you can utilize SIMD instructions. I know what I wrote wasn't clear on this, I was writing it in a hurry, sorry about that.

The reason I talk in cache lines, is because it's taking the real world aspect into the analysis of the algorithm. A theoretical analysis, while valuable in some aspects, are very far from the real world scenarios. I have done countless theoretical analysis of algorithms, found the actual (hidden) constants in big-O ect. but it just doesn't model the real world very well. This is the exact reason you see many fast algorithms use a naive, but cache friendly algorithm once the input is sufficiently small (e.g. with a divide and conquer algorithm).

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

#86

Post by anomalizer »

snewman wrote: post #17
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…

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…

netty's buffer management libraries do a good job at what you are looking for. Having an instance of the pooled allocator that is configured to prefer "direct" i.e. off heap memory might just be the thing.

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

#87

Post by to3m »

shantanugoel wrote: post #84
to3m wrote: post #62

Earlier quoted context omitted.

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…

Aside to the discussion, can you point out a link to the changes you did? I'd like to get silver searcher faster as well on windows.

Sure. Here's a binary: https://github.com/tom-seddon/the_silver_searcher/tree/_vs20...

The source code is there too, but I wouldn't look too closely. "Cobbled together", like I said. Though I've been using it all the time, in conjunction with ag-mode - https://github.com/Wilfred/ag.el - and haven't noticed any obvious problems.

Post reply on HN