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

The One Billion Row Challenge

morling.dev

Post reply on HN
Print view View original

71–80 of 366 posts

Re: The One Billion Row Challenge

#71

Post by bayindirh »

vinay_ys wrote: post #68
bayindirh wrote: post #56

Earlier quoted context omitted.

Then, your VM is not the only VM sharing the bare metal. Same thing applies, only on a slightly higher level. As long as you share the metal with other stuff (be it containers, binaries, VMs), there's always competition for resources, and your average time becomes your real world time.

Physical memory is not fungible like that across VMs. So, you can expect stuff loaded into memory to stay there unless your kernel inside the VM decides it not to.

No, it's. VirtIO's balooning device can "inflate" to pseudo-allocate memory on a VM to free physical memory for other hosts.

Moreover, even if your files in memory, you cannot reserve "memory controller bandwidth". A VM using tons of memory bandwidth or a couple of cores in the same NUMA node with your VM will inevitably cause some traffic and slow you down.

Re: The One Billion Row Challenge

#73

Post by lessbergstein »

ako wrote: post #22
lessbergstein wrote: post #14

I don't understand, it should be pretty easy. A rolling average with BigDecimal would probably be sufficient but a scientific lib might be better for a rolling average or more than a hundred million numbers. https://stackoverflow.com/questions/277309/java-floating-poi...

The difficulty is creating the fastest implementation. If you look at the results of the submissions so far you’ll see a big difference in duration, between 11 seconds and more than 4 minutes. 11 seconds seems pretty impressive for a 12Gb file. Would be interesting to know what programming language could do it faster. For a database comparison you’d probably want to include loading the data into your database for a f…

Perl would do it quite fast and it has the benefit of accessing posix primitives directly.

Re: The One Billion Row Challenge

#74

Post by eru »

fny wrote: post #17
Animats wrote: post #15

Earlier quoted context omitted.

It looks like the problem is dominated by reading in the data file. Some fast solutions just read the whole file into memory.

Rather than read the file into memory, memory mapping can be used.

Memory mapping (at least on Linux) isn't actually faster than reading the file manually. Especially if you use appropriately sized buffers.

(Of course, the five times in a row might mess with that.)

Re: The One Billion Row Challenge

#75

Post by kaba0 »

pkolaczk wrote: post #39
kaba0 wrote: post #32

Earlier quoted context omitted.

Java build times are very fast. You are just measuring your internet speed here. (Also, gradle is faster as a build tool for incremental compilation)

Gradle is faster than what? Than maven? Maybe. But not than Go or Cargo.

What step are we talking about? Javac itself is absolutely on the same order of magnitude speed as Go per loc, while rust is significantly slower (which makes sense, the latter is a properly optimizing compiler with heavy static analysis, while the former two just spews out java byte code/machine code).

Gradle with a daemon is also pretty fast, you are just probably used to some complex project with hundreds of dependencies and compare it to a cargo file with a single dependency.

Re: The One Billion Row Challenge

#76

Post by eru »

charcircuit wrote: post #37
pclmulqdq wrote: post #27

Earlier quoted context omitted.

You wouldn't want to do this for a huge file. A very fast solution would use a small number of buffers and io_uring (or equivalent), keeping the page table and cache footprint small.

What is the downside of memory mapping in this scenario? Shouldn't the page table properly handle the case of doing a single sequential read over a range of pages? Accessing the contents of a file doesn't seem like something caching would matter for. Do you mean that reading of sequential pages will keep adding to the cache compared to reading from a single page? That seems like a similar thing as before where they w…

> Shouldn't the page table properly handle the case of doing a single sequential read over a range of pages?

That's what I used to think, too. But the kernel ain't that smart.

Re: The One Billion Row Challenge

#77

Post by kaba0 »

sixlelyt321 wrote: post #65
kaba0 wrote: post #32

Earlier quoted context omitted.

Java build times are very fast. You are just measuring your internet speed here. (Also, gradle is faster as a build tool for incremental compilation)

But run time is slow, is that you want to convey?

No, I would even go as far as to say that a naive, non-microbenchmark java program can often perform better than a naive, low-level language one.

Re: The One Billion Row Challenge

#78

Post by somat »

Animats wrote: post #15
kriskrunch wrote: post #10

Earlier quoted context omitted.

Check out the discussion[0], looks like there are submissions in several languages. Go, Rust, Python, and C++, to name a few [0] https://github.com/gunnarmorling/1brc/discussions

It looks like the problem is dominated by reading in the data file. Some fast solutions just read the whole file into memory.

It would be a more interesting challenge if the data file were larger than the memory. I would love to see what people would come up with on some baby vm with 512 mb of ram.

Even more interesting would be small ram, little local storage and a large file only available via network, I would like to see something other than http but realistically it would be http.

Re: The One Billion Row Challenge

#79

Post by chmod775 »

jalino23 wrote: post #19
baq wrote: post #12

Earlier quoted context omitted.

Why would I use Hadoop for such a small number of rows…?

1 billion is small for hadoop?

Anything that fits in RAM on one machine is easily too small for Hadoop. In those cases, the overhead of Hadoop is going to make it get destroyed by a single beefy machine. The only times where this might not be the case is when you're doing a crazy amount of computation relative to the data you have.

Note that you can easily reach 1TB of RAM on (enterprise) commodity hardware now, and SSDs are pretty fast too.

Old but gold post from 2014: https://adamdrake.com/command-line-tools-can-be-235x-faster-...

Re: The One Billion Row Challenge

#80

Post by gerikson »

lessbergstein wrote: post #73
ako wrote: post #22

Earlier quoted context omitted.

The difficulty is creating the fastest implementation. If you look at the results of the submissions so far you’ll see a big difference in duration, between 11 seconds and more than 4 minutes. 11 seconds seems pretty impressive for a 12Gb file. Would be interesting to know what programming language could do it faster. For a database comparison you’d probably want to include loading the data into your database for a f…

Perl would do it quite fast and it has the benefit of accessing posix primitives directly.

A naive perl solution is really really slow compared to even the reference Java implementation. (I know, I've tried)
Post reply on HN