Support city names up to 100bytes

[buybackoff]

https://github.com/gunnarmorling/1brc/blob/main/create_measurements3.sh

[RagnarGrootKoerkamp]

Is this one of the tests with long city names? Yes those won't work. Not yet anyway; I may support them eventually but for now I don't really care.

[buybackoff]

The specs say up to 100 bytes. If it does not work with that it's not valid.

[RagnarGrootKoerkamp]

Well I state my assumptions at the top of the readme and blogpost. I'll first push for max performance and may make it pass tests at some later point if I feel like it. Developing is faster if I don't have to care about correctness for now.

[buybackoff]

If it doesn't work, it doesn't matter how fast it doesn't work 😉

It's very convenient to limit an entire line to one AVX vector... Definitely not valid for comparison with other conformant implementations ATM.

[RagnarGrootKoerkamp]

Well, I could fix this. But still then perfect hashing assumes that all cities names appear in some reasonable prefix of the data.

Sure I could make the code pass tests, just by writing an if statement if I see a long city name and then doing completely different code, but that's also lame...

[buybackoff]

Sure I could make the code pass tests, just by writing an if statement if I see a long city name and then doing completely different code, but that's also lame

Please do. At the moment you are around the fastest on the default data. But not conforming to the specs makes the comparison invalid.

[RagnarGrootKoerkamp]

Ok I think this should be fixed now. Could you test again?

(But I wouldn't be surprised if there are some other things that fail. In that case I'll just generate the files myself and test locally.)

[tivrfoa]

Ok I think this should be fixed now. Could you test again?

(But I wouldn't be surprised if there are some other things that fail. In that case I'll just generate the files myself and test locally.)

I just ran your program, and it prints wrong averages.

I'm testing with only 200 million rows, created with create_measurements.sh

Correct is on the left:

[RagnarGrootKoerkamp]

Oh indeed. There was a bug in my verification script so I missed this. The factor 2 off is fixed now. I did another optimization that I thought was correct, but it turns out that the temperature for Baghdad now is off by 0.1. I may revert that change at some point if needed.

[buybackoff]

@RagnarGrootKoerkamp could you tell, as a gentleman, if your current version is compliant to the best of your knowledge? Or at least if existing bugs won't affect performance by more than 10s of millis?

If so, you are No 1 with a huge margin. I will trust your word 😄 (but that will be public soon)

[RagnarGrootKoerkamp]

I'm pretty sure it's completely not compliant. I'm pretty sure I could make it pass all tests in a somewhat 'clean' way without loosing too much performance, but even then, I'm violating these rules:

No external library dependencies may be used

I use some small unsignificant utility libraries which is fine IMO, but I also use (my own) crate for perfect hashing. That in itself is quite a large codebase. On the other hand, I'm only using a small part of it and may inline it so I can optimize it for the specific dataset here.

But more importantly:

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 distribution (number of measurements per station) must be supported

I currently rely a lot on the fact that each row contains a random city name. I can't handle cases where, say, a city only starts appearing somewhere halfway through the data.
I don't think any of the current testcases tests this, but still. There is a very big difference between passing all tests and having code that can reliably handle any dataset within these constraints.

See also this discussion.

I'm also relying on the fact that cities are uniquely determined by their first and last 8 characters. Thus, cities AAAAAAAAXAAAAAAAA and AAAAAAAAYAAAAAAAA currently are indistinguishable to my code.

Everything is kinda in a complicated state: of course I could also do some detection of the number of cities and their properties, and if they look enough like the eval set choose the fast path, and otherwise choose a slower fallback. It's somewhat unfortunate the eval set is a single file with very specific properties. It would have been better if the time was the sum over a number of completely different types of input, but that is not the case, so I am just squeezing everything I can out of this one eval input file.

[buybackoff]

Oh, alright. I wondered what magic you've applied for 10K dataset that it is as fast...

Understood. Thank you, Sir!

[RagnarGrootKoerkamp]

Ah I found your unofficial leaderboard now :)

I really should try to make my solution a bit more compliant to the point where I think it's fair to include it.

Either way, things are around 30% faster now compared to my last message here, so I'm curious how it performs in your benchmarks compared to @lehuyduc.

You may want to try both -j6 and -j12. In my evals it's actually faster to disable hyperthreading, but given that it is enabled on the machine, probably -j12 is better.

[buybackoff]

That leaderboard is quite stale. It would be great if you could make it work with 10K data by tomorrow mid-day approximately. It would be even greater is the solution remains fast with that data.