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

351–360 of 366 posts

Re: The One Billion Row Challenge

#351

Post by corlinpalmer »

dvko wrote: post #340
corlinpalmer wrote: post #325

Here's my implementation in Go, which runs in under 5 seconds. It doesn't use anything too obscure, only the built-in maps and no external libraries. It's also the fastest solution I've tested on my M3 Pro Mac. Eager to see what beats it! https://gist.github.com/corlinp/176a97c58099bca36bcd5679e68f...

There’s an implementation in C which should run in well under 2 seconds on your M3. https://github.com/dannyvankooten/1brc

Under 2 seconds seems rather impossible on my machine since the disk maxes out at 5.1 GB/s. This one ran in 7.4s on my M3:

`bin/analyze measurements.txt 30.34s user 16.28s system 629% cpu 7.406 total`

Re: The One Billion Row Challenge

#352

Post by corlinpalmer »

guss_bro wrote: post #331
corlinpalmer wrote: post #325

Here's my implementation in Go, which runs in under 5 seconds. It doesn't use anything too obscure, only the built-in maps and no external libraries. It's also the fastest solution I've tested on my M3 Pro Mac. Eager to see what beats it! https://gist.github.com/corlinp/176a97c58099bca36bcd5679e68f...

The fastest java solution from the current leaderboard runs within 2.6 seconds in my brand new M3 Mac.

Is that `./calculate_average_royvanrijn.sh`? It runs in 6.7s for me.

I would love it if you could run my solution and compare!

Re: The One Billion Row Challenge

#353

Post by pbh101 »

bayindirh wrote: post #334
pbh101 wrote: post #329

Earlier quoted context omitted.

But this is a contrived test, and looking for the fastest solution, so your arguments point to taking the fastest: the one with the least interference.

Yes, the one works the fastest in average case will be the fastest in the real world, and will be the one least affected by general noise present in the system. The test is very well designed, we may say.

I agree that this method will produce a better estimate of expected mean real world performance under certain load conditions, but still contend it just muddies the waters about which solution is in fact the fastest.

And here is Andrei Alexandrscu arguing the same in 2012: https://forum.dlang.org/thread/mailman.73.1347916419.5162.di...

Re: The One Billion Row Challenge

#354

Post by dvko »

corlinpalmer wrote: post #351
dvko wrote: post #340

Earlier quoted context omitted.

There’s an implementation in C which should run in well under 2 seconds on your M3. https://github.com/dannyvankooten/1brc

Under 2 seconds seems rather impossible on my machine since the disk maxes out at 5.1 GB/s. This one ran in 7.4s on my M3: `bin/analyze measurements.txt 30.34s user 16.28s system 629% cpu 7.406 total`

On most Linux distributions and when the file is mmap'd, if you run it a second time the data will still be in RAM and not have to be read from disk. This gets the runtime down to 1.1s for this AMD 2950x (https://github.com/gunnarmorling/1brc/discussions/46#discuss...).

With SIMD and certain assumptions about the input this can seemingly be further reduced to well under a second, eg see https://github.com/gunnarmorling/1brc/discussions/138.

Re: The One Billion Row Challenge

#355

Post by nojvek »

usefulcat wrote: post #250
toth wrote: post #243

Earlier quoted context omitted.

You don't need the look up table. All you are asked for is min/mean/max which can all be computed in one pass without storing the data. All you need is a hash table with 400 entries and 3 floats (running min, mean and max) and and int (count, for updating running mean). That's just 16 bytes, if you use 16 bytes for name of station you can fit everything under 16K. IO will dominate the running time for this, and JSON…

> IO will dominate the running time for this, and JSON parsing will be second. Memory bandwidth might dominate, but probably not I/O. The input file is ~12GB, the machine being used for the test has 32GB, and the fastest and slowest of five runs are discarded. The slowest run will usually be the first run (if the file is not already cached in memory), after which there should be little or no file I/O.

Is there a way to validate from app whether all file pages are cached in memory?

What if the code was run against constraints such as Max memory limit in a docker container.

Re: The One Billion Row Challenge

#357

Post by ykonstant »

gunnarmorling wrote: post #180
thomaswue wrote: post #136

Earlier quoted context omitted.

What are the constraints on station names - i.e. min length, max length, maximum number of different names?

Just clarified this in the README: * Input value ranges are as follows: - Station name: non null UTF-8 string of min length 1 character and max length 100 characters - Temperature value: non null double between -99.9 (inclusive) and 99.9 (inclusive), always with one fractional digit * Implementations must not rely on specifics of a given data set, e.g. any valid station name as per the constraints above and any data…

The README says max length 100 bytes, which I suppose we can (?) assume are octets. Also, it mentions that you can assume the station string does not contain the separator ';'.

I guess the station string is also supposed to be free of control characters like newlines, though spaces are allowed. This, however, is not stated.

Re: The One Billion Row Challenge

#358

Post by anonymoushn »

AUnterrainer wrote: post #356

My one liner solution runs in 76ms on my 10 year old mac. q)\ts exec (min;max;avg)@\:measurement by city from flip `city`measurement!("SF";";") 0: `:weather_stations.csv 76 8720688

Your 10 year old mac can ingest the input at 157GB/s? Is that from RAM or from disk?

Re: The One Billion Row Challenge

#359

Post by AUnterrainer »

anonymoushn wrote: post #358
AUnterrainer wrote: post #356

My one liner solution runs in 76ms on my 10 year old mac. q)\ts exec (min;max;avg)@\:measurement by city from flip `city`measurement!("SF";";") 0: `:weather_stations.csv 76 8720688

Your 10 year old mac can ingest the input at 157GB/s? Is that from RAM or from disk?

Actually I only had a partial file :/ didn't realise that the file in the data folder was only a sample

Re: The One Billion Row Challenge

#360

Post by ftisiot »

yencabulator wrote: post #346
ftisiot wrote: post #189

Earlier quoted context omitted.

Just modified the original post to add the file_fdw. Again, none of the instances (PG or ClickHouse) were optimised for the workload https://ftisiot.net/posts/1brows/

Not including this in the benchmark time is cheating: \copy TEST(CITY, TEMPERATURE) FROM 'measurements.txt' DELIMITER ';' CSV;

The loading time it's included in both examples

In the first one, the table is dropped, recreated, populated and queries. In the second example, the table is created from a file FDW to the CSV file. In both examples the loading time is included in the total time

Post reply on HN