Comment by lifeisstillgood | Hacker News Reader

Comment by lifeisstillgood | Hacker News Reader

Parent Full thread

lifeisstillgood

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 rewinding to the front of the tape cost you several minutes of (expensive) waittime.

Imagine a scenario where these guys design how to stream logs to the disk to maximise streaming reads, then optimise reading that out to SSD thence to RAM and L2 and so forth. All designed to drive text past a regex running at bazillions of times a second.

Lets call it the New Brute Force, where its just as much effort to get out the door as elegant algorithms, but it is much much much simpler. And of course, sells more hardware.

Expect to see Intel Inside wrapped around the New Brute Force any time soon :-)

Edit: And they used Java ! I was expecting low-level C optimisations all over the place

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 server logs have a very high write-to-read ratio really helps us out here.

Today, we're keeping everything on SSD -- twice, in fact, to maintain a hot spare for each server. SSD prices have fallen to the point where, even renting from Amazon, we can make the cost model work; and SSD is a great crutch as we tune our storage layer. But spinning disk will be a lot cheaper.

As for Java: we've been pretty surprised ourselves. Going in, we expected to need a lot more "native" (C) code. As it turned out, currently the only non-Java code we're using is the LZ4 library, and even there we only recently moved to the non-Java implementation. We do soon expect to move a few more bits of code to C, such as the core text-search loop. But based on the performance we've been getting in pure Java, we don't anticipate any need to move more than a fraction of 1% of our overall code base.

We do have some code that lives in a sort of middle ground -- Java code written like it was in C. Our database buffers live in a set of 2GB byte arrays, soon to be replaced by native memory blocks. We do our own (very simple) memory allocation within that, and use a sprinkling of Unsafe operations to access it. This gets us closer to C performance (not all the way there), without any of the hassles of bridging across languages. This part is still well under 1% of our overall codebase.

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.

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.

Maybe we are talking about different abstractions. Perhaps libraries? I reimplemented (probably badly) session handling code in wsgi (python) - because the Django code was over 2000 lines long and used other libraries and I did not understand it - especially when all I wanted was to store a 128bit number in a client cookie and then look it up when I saw it again.

So the idea is simple (cookie sessions) but the different ways of implementing it can hold complexity, errors and abstractions.

There is nothing stopping the same happening with Haskell - I can I am sure write terrible code even in the best languages (see my entire output for proof :-)

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

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.

I just remember a documentary / interview - iirc a five minute interview at a trade show. It stuck in my head. I am afraid I cannot find the link now but trade show / two people sitting down, a demo of oculus rift then comments.

I remember reading "Latency Mitigation Strategies", by Carmack. It doesn't mention the Oculus except in an acknowledgment at the end, but it might be about the same thing lifeisstillgood is talking about:

http://www.altdevblogaday.com/2013/02/22/latency-mitigation-...

HN discussion: https://news.ycombinator.com/item?id=5265513

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.

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.

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.

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 from the (spinning) disk.

And on using Java. It's actually pretty fast, and certainly fast enough for a prototype. Once you have the stack build, you can benchmark and optimize the bits that needs to be optimized, usually this means C or handcrafted ASM.

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.

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

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.

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.

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

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.

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

Reply on news.ycombinator.com