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

291–300 of 366 posts

Re: The One Billion Row Challenge

#291

Post by kaba0 »

krzyk wrote: post #266
troupo wrote: post #242

Earlier quoted context omitted.

> Absolutely false. A 3-4 lines gradle build file for java will be fast, and correctly parallelize and maximally utilize previously built artifacts. I've never seen this on any project that utilizes gradle. Every time, without fail, it's a multi-second startup of gradle that eventually invokes something that is actually fast: javac. > I’m getting the feeling that you have zero idea about what you talk about. Only 7 y…

They are trying to make gradle better, by implementing a "maven over it" - declarative build configuration. But for time being maven is way easier to configure and understand.

It has always been “an imperative code that outputs the declarative configuration that can be used for the build”. Which is a very reasonable thing to do, but unfortunately most people fail to understand that a println in the config file’s global scope is different than inside a closure for a task description.

Re: The One Billion Row Challenge

#292

Post by londons_explore »

toth wrote: post #278
londons_explore wrote: post #255

Earlier quoted context omitted.

Merely finding the start/end of each line will use more computation (in the inner loop) than the approach I outlined. Let alone converting the number from ascii to a float, or looking up the place name in a has table (oh, and the name is variable length, so you're gonna need to find how long the name is first).

I deleted two previous comments because I realized I misunderstood your proposal. I understand it better now, but I am still confused about something... Your state machine would need at least 2*160,000 states (you need an extra bit to flag whether you have reached a newline in the last word and need to increment a counter or not), correct? And you are assuming the input is 4 bytes, so won't your transition table need…

The states don't need to map 1:1 with cities or temperatures. They merely need to encode all information collected so far which is still relevant. They also don't need to represent all possible situations - anything that is super rare (eg. temperature of 95C) can simply be diverted to a special "invalid" state which triggers regular code to take over for those few entries.

Re: The One Billion Row Challenge

#293

Post by LegionMammal978 »

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…

> With just 32 bits of state, with AVX512 we can be running 512 copies of this in parallel if we like, per core! AKA, compute will not be the bottleneck.

How can the state machine be run in parallel, when the next state always has a dependency on the previous state?

Also, how exactly would the state register be decoded? After you XOR it with 4 bytes of input, it could be practically any of the 4.7 billion possible values, in the case of an unexpected place name.

And even for expected place names longer than 4 bytes, wouldn't they need several states each, to be properly distinguished from other names with a common prefix?

Re: The One Billion Row Challenge

#294

Post by Animats »

eru wrote: post #74
fny wrote: post #17

Earlier quoted context omitted.

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

Right, it's the five times in a row thing that makes an in-memory solution faster. Otherwise, this is a purely sequential one-pass problem, which is how you'd do it in practice.

Parallelism with edge effects is pretty common. Weather simulation, finite element analysis, and big-world games all have that issue. The middle of each cell is local, but you have to talk to the neighbor cells a little.

Re: The One Billion Row Challenge

#295

Post by promiseofbeans »

winrid wrote: post #97
wiseowise wrote: post #94

Earlier quoted context omitted.

Ok, I’ll bite - why?

It looks like they mostly work in JS, so maybe it's the type definitions that look clunky. Java is explicit, yes. This is intentional :)

Funny thing is, most js devs do typescript now, which is the same as java, of not worse because you need an extra colon for your static types

Re: The One Billion Row Challenge

#296

Post by promiseofbeans »

estiaan wrote: post #270
brrrrrm wrote: post #236

Earlier quoted context omitted.

it feels like the characters-typed to functionality ratio is quite low. at the same time, the code isn't much cleaner and there's a lot of mental overhead in deciphering the abstractions (in this case Collector).

Java is probably the language I use the most but I hate how much boilerplate it has. Something I’ve found to help with that is using Java Records instead of classes, a record is kind of like a struct, but I don’t think it’s exactly the same, there’s no boilerplate and something I quite like about them is that their fields are immutable (more specifically “private final”) which works well with more functional programm…

> instead of things being like “pos.add(5)” if pos is a record you need to reassign it like “pos = pos.add(5)”... That's just mutable vs immutable data structures

Re: The One Billion Row Challenge

#297

Post by londons_explore »

alkonaut wrote: post #217
jerf wrote: post #172

Earlier quoted context omitted.

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…

It's easier than you think... utf-8 guarantees that all bytes of a multi-byte character have the high bit set. 0x3B (semicolon) does not have the high bit set. Therefore 0x3B is guaranteed to be your seperator.

The same logic applies to newline - therefore, you can jump into the middle of the file anywhere and guarantee to be able to synchronize.

Re: The One Billion Row Challenge

#298

Post by anonymoushn »

londons_explore wrote: post #226
Jaxan wrote: post #215

Earlier quoted context omitted.

Go for it!

You nerd sniper you! But more seriously, the JVM's support for vector intrinsics is very basic right now, and I think I'd spend far more time battling the JVM to output the code I want it to output than is fun. Java just isn't the right language if you need to superoptimize stuff. Theoretically all of the above is super simple SIMD stuff, but I have a suspicion that SIMD scatter/gather (needed for the state lookup ta…

It sounds like you're unfamiliar with vectorized string processing tasks, so you could surely learn a lot by working on an implementation of the proposed approach. I think it's fine to make it in C++ and then port to Java.

For more such tasks you could go to highload.fun.

Re: The One Billion Row Challenge

#299

Post by brrrrrm »

promiseofbeans wrote: post #295
winrid wrote: post #97

Earlier quoted context omitted.

It looks like they mostly work in JS, so maybe it's the type definitions that look clunky. Java is explicit, yes. This is intentional :)

Funny thing is, most js devs do typescript now, which is the same as java, of not worse because you need an extra colon for your static types

Weird to think typescript is similar to a language that requires a class definition for “hello world” lol. You can’t even fit it on a single 80 character line…

Re: The One Billion Row Challenge

#300

Post by sfn42 »

johndough wrote: post #112
gunnarmorling wrote: post #95

Earlier quoted context omitted.

Their should be no optimizations which rely on a-priori knowledge of the dataset. I.e. if you calculate a perfect hash function at runtime by inspecting the dataset, that's fine (not sure whether it's beneficial), but hard coding it, is not.

That is a tricky rule to enforce. For example, some solutions assume that the temperature values fit into an int, which could be interpreted as relying on a priori knowledge.

Somehow I doubt any weather station would register temperatures above 2,14 billion degrees
Post reply on HN