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

211–220 of 366 posts

Re: The One Billion Row Challenge

#211

Post by apwheele »

jackhalford wrote: post #170
solarized wrote: post #123

Just for fun. Speed testing awk vs Java. awk -F';' '{ station = $1 temperature = $2 sum[station] += temperature count[station]++ if (temperature max[station] || count[station] == 1) { max[station] = temperature } } END { for (s in sum) { mean = sum[s] / count[s] printf "{%s=%.1f/%.1f/%.1f", s, min[s], mean, max[s] printf (s == PROCINFO["sorted_in"][length(PROCINFO["sorted_in"])] ? "}\n" : ", ") } }' measurement.txt

Your sum variable could get pretty large, consider using the streaming mean function, something like: new_mean = ((n*old_mean)+temp)/(n+1)

Had this same thought as well. Definitely comes up when calculating variance this way in streaming data.

https://stats.stackexchange.com/a/235151/1036

I am not sure if `n*old_mean` is a good idea. Wellford's is typically something like inside the loop

count += 1; delta = current - mean; mean += delta/count;

Re: The One Billion Row Challenge

#212

Post by brrrrrm »

mgaunard wrote: post #208
londons_explore wrote: post #202

Earlier quoted context omitted.

This assumes the file is already in page cache, and therefore already in RAM. The 0.3 seconds is the time to get it from RAM to the CPU L3 cache.

That sounds like cheating. The exercise says to process a large file that's on disk. If the data is in RAM then that's a whole different game.

Isn’t it run multiple times and the slowest is dropped? Why would you expect the file to be evicted from ram so quickly?

Re: The One Billion Row Challenge

#213

Post by rockwotj »

mgaunard wrote: post #208
londons_explore wrote: post #202

Earlier quoted context omitted.

This assumes the file is already in page cache, and therefore already in RAM. The 0.3 seconds is the time to get it from RAM to the CPU L3 cache.

That sounds like cheating. The exercise says to process a large file that's on disk. If the data is in RAM then that's a whole different game.

The benchmark is run 5 times without flushing file system caches. If you mmap it, it will still be in memory between process runs. The author intended this FWIW

Re: The One Billion Row Challenge

#214

Post by hknmtt »

sudodudeo wrote: post #169
hknmtt wrote: post #129

Earlier quoted context omitted.

actually i think you can also just average each chunk and then add it to existing data. like read N rows(say all have one location to keep it simple), average the data from the chunk, update/save min and max, move on to next chunk, do the same but now update the average by adding to existing/previously computed average and divide by two. the result will be the same - disk IO will be the most limiting aspect. this "ch…

Wouldn't this end up reducing the weight of earlier records by repeatedly dividing them into smaller chunks? I.e. avg of {22.5, 23, 24} = 23.17... But: 1. 22.5 2. (22.5 + 23)/2 = 22.75 3. (22.75 + 24)/2 = 23.375

say you load 1 million records and you average them at 5.1. you then load another million and average them at 4.5. so you 5.1+4.5=9.6/2=4.8. rinse and repeat. as long as you keep the amount of records processed per each run about the same, your numbers will not be skewed. only the last chunk will most likely be smaller and it will introduce small rounding error, like if it has only 10k records instead of 1M. but still it is the simplest solution with good enough outcome.

Re: The One Billion Row Challenge

#215

Post by Jaxan »

londons_explore wrote: post #207

I believe the whole thing can be done in 0.3 seconds with the following approach: (Describing only the 'happy path' here - other paths can be made fast too, but will require different implementations) * Since temperatures are only to 0.1 decimal points, we have a finite number of temperatures. ~400 temperatures will cover all common cases. * We also have a finite number of place names. (~400) * Just make a lookup tab…

Go for it!

Re: The One Billion Row Challenge

#216

Post by menaerus »

londons_explore wrote: post #202
menaerus wrote: post #192

Earlier quoted context omitted.

> The total file is ~12 gigabytes, so we should expect to be able to get the task done in 0.3 seconds or so. How? EPYC-Milan features PCIe 4.0 and theoretical maximum throughput of x4 sequential read is ~8GB/s. In bare-metal machines, this figure is rather closer to 5-6GB/s, and in cloud environments such as CCX33, I imagine it could be even less. So, unless I am missing something you'd need ~2 seconds only to read t…

This assumes the file is already in page cache, and therefore already in RAM. The 0.3 seconds is the time to get it from RAM to the CPU L3 cache.

That makes sense now, thanks.

Re: The One Billion Row Challenge

#217

Post by alkonaut »

jerf wrote: post #172
londons_explore wrote: post #164

Earlier quoted context omitted.

UTF-8 makes this far harder... But if you stick to the letter but not spirit of the rules, you can simply fall back to a slow implementation if you ever detect any byte > 127 (indicating a multibyte UTF-8 character).

Only if you validate the UTF-8 as being valid. If you just accept that it is you can treat it as just some bytes. Nothing in the spec I see requires processing UTF-8 as an actual Unicode string. The easiest way to handle Unicode is to not handle it at all, and just shove it down the line. This is often even correct, as long as you don't need to do any string operations on it. If the author wanted to play Unicode game…

Since the tail of the line has a known format I guess we are rescued by the fact that the last 0x3B is the semicolon as the rest is just a decimal number. We can’t know the first 0x3B byte is the semicolon since the place names are only guaranteed to not contain 0x3B but can contain 0x013B. So a parser should start from the rear of the line and read the number up to the semicolon and then it can treat the place name as byte soup. Had two places shared line this challenge would have required real utf parsing and been much harder.

Re: The One Billion Row Challenge

#218

Post by jodrellblank »

londons_explore wrote: post #207

I believe the whole thing can be done in 0.3 seconds with the following approach: (Describing only the 'happy path' here - other paths can be made fast too, but will require different implementations) * Since temperatures are only to 0.1 decimal points, we have a finite number of temperatures. ~400 temperatures will cover all common cases. * We also have a finite number of place names. (~400) * Just make a lookup tab…

Where does your ~160,000 come from? There's a billion rows, couldn't there be a different place on every row giving a billion place names?

Re: The One Billion Row Challenge

#219

Post by londons_explore »

jodrellblank wrote: post #218
londons_explore wrote: post #207

I believe the whole thing can be done in 0.3 seconds with the following approach: (Describing only the 'happy path' here - other paths can be made fast too, but will require different implementations) * Since temperatures are only to 0.1 decimal points, we have a finite number of temperatures. ~400 temperatures will cover all common cases. * We also have a finite number of place names. (~400) * Just make a lookup tab…

Where does your ~160,000 come from? There's a billion rows, couldn't there be a different place on every row giving a billion place names?

There are only ~400 place names in the generated data. 160,000 = 400*400

The state machine generation would need to know all 400 - but it's easy enough to scan the first few hundred thousand rows to find them all, and have a fallback incase a name is seen that has never been seen before. (the fallback would be done by having the state machine jump to an 'invalid' state, and then at the end you check that that invalid state's counter is zero, and if it isn't, you redo everything with slow code).

Re: The One Billion Row Challenge

#220

Post by kaba0 »

pkolaczk wrote: post #193
kaba0 wrote: post #167

Earlier quoted context omitted.

Scala is a much different case, it has one of the most advanced type systems, many implicit scoping rules etc. Even a java change that might affect the scala codebase could result in a slow incremental build. Also, the build system may not have been as modular as it could. In my experience, java annotations gets processed very fast.

> it has one of the most advanced type systems Well, that's a bit of a stretch. It is definitely one of the most complex type systems due to interactions between nominal sub-typing and type classes which is a bit hairy. But in terms of what this type system can express or prove, it's both inferior (cannot express lifetimes or exclusive access) and superior (HKTs, path dependent types) to Rust in some aspects. Let's s…

> It is definitely one of the most complex type systems due to interactions between nominal sub-typing and type classes

That’s what I meant mostly. Though if I’m being honest, I’m not familiar with the implementation of either language’s type system.

Post reply on HN