A nice challenge for performance suckers, the 1 billion row challenge in Ada?

General
1

Hi all,

this is just a quick post in case someone is interested in make code go fast, really fast.

Recently, a repository about testing how fast Java could be doing operations in a 1 Billion entries file, became quite popular. Other language communities have picked up the hype/trend and are now creating their own solutions and comparing them.

In case someone is interested in giving this a good try, go ahead and show the world what Ada can do! Here is the repo that started it all GitHub - gunnarmorling/1brc: 1ļøāƒ£šŸšŸŽļø The One Billion Row Challenge -- A fun exploration of how quickly 1B rows from a text file can be aggregated with Java

Best regards,
Fer

4 Likes
2

Yeah, alright, but someone else will need to spread it around on Hacker News and similar spaces for me.

3

I donā€™t see why not :slight_smile:

4

Charlie would do this with DSA.

1 Like
5

Here:
http://verisimilitudes.net/2024-01-30

Iā€™ve been unable to test this on the full input file, and my statistics will be worthless anyway due to the machine I use, but it should work nonetheless.

6

Nice work @Verisimilitude!

I gave your program a spin :slight_smile: Here is how it went:

I downloaded both the program and the trie library. I tested it with the supplied data/weather_stations.csv file. However, I had to delete the initial comments of that file and bump the number of allowed city names to 40_000 as that file has very few duplicates (it has about 45k entries). I love Ada for how easy it is to debug :smiley: Finding the ā€œcommentsā€ issue was easy, finding that the supplied sample file had more that 10_000 distinct entries was also fairly simple thanks to exceptions and GDB catch exception and catch assert :smiley:

The command I used during debugging was: gnatmake -g3 -ggdb -f 1brc.adb -o 1brc_debug
For the optimised binary I used: gnatmake -march=native -O3 -f -gnato0 -gnat2022 -gnatB -gnatp -flto 1brc.adb -o 1brc_optim -largs -s

I could not measure a difference between the two binaries is such a small input. Most of the time is spent printing on the terminal x) My hardware supports AVX-512 (AMD Ryzen 7840HS). However, I found that there are not many AVX-512 instructions generated. but AVX2/AVX was used extensively.

I am trying to fix my Java/Maven installation so that I can generate a 1B sample file and test it a bit more.

Thank you!!!

Update:

I managed to get my Java and Maven system going and I generated a 1 billion entry file (13 gigs). I ran the provided baseline program to have a verified result. Here is what I got.

The debug build takes about 2mins and 20 secs. The optimised build takes 1min 57 secs. The provided baseline program (java) takes 2mins 30 secs.

However, the results of your program are not the same as the baselineā€¦ I ran a diff to make sure that the generated results were the same but some numbers are clearly different from the baseline (it is not just formatting). Here is an example:

Baseline

{Abha=-32.3/18.0/67.2, Abidjan=-20.6/26.0/76.0, AbƩchƩ=-22.2/29.4/76.1, Accra=-30.1/26.4/78.2, Addis Ababa=-31.8/16.0/66.9,

Optimised/Debug

{Abha=-32.3/ 67.2/ 17.9, Abidjan=-20.6/ 76.0/ 26.0, AbƩchƩ=-22.2/ 76.1/ 29.4, Accra=-30.1/ 78.2/ 26.4, Addis Ababa=-31.8/ 66.9/ 15.9,

Apart from the order being different and some extra whitespacing (which I believe comes from Adaā€™s librariesā€¦), the first result is incorrect. The average temp for Abha should be 18.0, but the Ada program says it is 17.9ā€¦ Maybe there is some issue with fixed point precision?

I hope this helps,
Fer

1 Like
7

I sincerely appreciate this testing, which I was unable to do. I reviewed the GitHub page for the contest, see that I got the ordering of the values wrong in printing, and also noticed that the rounding mode of floating point was specifically specified. It should be possible to make Temperature and Average appropriate floating point types with no changes to the program; Iā€™m also curious to see if decimal fixed point solves this problem, and what its performance characteristics would be. Iā€™ll update the little program later today. I wonā€™t bother to fix the extra space in printing, because that would be too hard for this little challenge.

Once again, I appreciate the help.

1 Like
8

Iā€™ve modified the program in-place to use floating point types, and I was forced to instantiate Ada.Text_IO.Float_IO twice over using the Image attribute. It should work better now.

There probably wonā€™t be too much interest in this after today, so if itā€™s going to be uploaded to Hacker News or other places, that should probably happen soon.

9

Quick update from my side. I used the newer Float package. I did not modify it and I tested it with the same input as the others. The program (compiled using optimised flags) tookā€¦ 2mins 26 secsā€¦ It is just as slow as the provided baseline program and quite a bit slower than the one used fixed point! Very interesting!!

Output from the baseline:

{Abha=-32.3/18.0/67.2, Abidjan=-20.6/26.0/76.0, AbƩchƩ=-22.2/29.4/76.1, Accra=-30.1/26.4/78.2, Addis Ababa=-31.8/16.0/66.9, Adelaide=-34.5/17.3/66.7, Aden=-20.0/29.1/75.9, Ahvaz=-22.6/25.4/78.9, Albuquerque=-37.4/14.0/64.9, Alexandra=-36.2/11.0/61.1,

Output from the ā€œfloatā€ program:

{Abha=-32.3/18.0/67.2, Abidjan=-20.6/26.0/76.0, AbƩchƩ=-22.2/29.4/76.1, Accra=-30.1/26.4/78.2, Addis Ababa=-31.8/16.0/66.9, Adelaide=-34.5/17.3/66.7, Aden=-20.0/29.1/75.9, Ahvaz=-22.6/25.4/78.9, Albuquerque=-37.4/14.0/64.9, Alexandra=-36.2/11.0/61.1,

The diff is still not the same as Ada prints always three digits/spaces ( 9.0), while the Java program does not (`9.0). But it seems to be about right!

Thank you for your work!

1 Like
10

Iā€™m not familiar with this package.

I should take a look at the baseline program and see how it compares. Iā€™d figure favorably.

Itā€™s no issue. Will the article be uploaded anywhere so that it gets some attention?

11

I meant the solution using floats instead of fixed point.

I will ask Jay if he can do it. I think it wold be interesting if there is a mention to both implementations (fixed point and floats) and the (basic) performance difference that was found.

12

Iā€™ll upload the fixed-point implementation again, and change the article, later today.

13

Iā€™ve made those changes.

14

Jay just published your blog post to Hacker News The One Billion row challenge in Ada | Hacker News Reddit The One Billion row challenge in Ada : ada Twitter, Mastodon, Lobsters and the BSD forum :slight_smile:

Hopefully some people notice it and see how clean and readable the code is ^^

2 Likes
15

Is your Trivial_Trie library available publicly? I might have a use case for itā€¦

16

http://verisimilitudes.net/2022-05-05

I plan to write a Less_Trivial_Trie library with more features soon enough.

1 Like