5 ms·

The whole problem is solvable with a single hashtable or a fixed set of memory. The solution use mmap over the input file. So no need for a GC run or a large he

The whole problem is solvable with a single hashtable or a fixed set of memory. The solution use mmap over the input file. So no need for a GC run or a large heap. The solutions also mostly used graalvm and ahead of time compilation.

dbacar 3y ago
..and all solutions use unsafe
- borissk 3y ago
  So it's better to write this sort of code in a language that's unsafe by default (e.g. C), rather than try to abuse Java. Reminds me of the code that Microsoft produced when they were trying to prove their new .NET Core is one of the fastest web runtimes - it was quite fast, but had nothing to do with the way C# code is written out there.
  - coldpie 3y ago
    > So it's better to write this sort of code in a language that's unsafe by default (e.g. C), rather than try to abuse Java. I'm not necessarily disagreeing, but can you elaborate on why it's better? Using unsafe for some parts of the code doesn't throw out safety guarantees about all of the rest of the code.
    - anonymoushn 3y ago
      In this case it's better because C users have access to vector intrinsics that are much cheaper than the ones Java users have access to.
    - pron 3y ago
      > Using unsafe for some parts of the code doesn't throw out safety guarantees about all of the rest of the code. That's actually hard to prove because you don't know which guarantees the unsafe code can break; being unsafe, it could potentially, say, mutate arbitrary final fields of any object in the program. So while such code doesn't necessarily break invariants, there's no easy way to tell whether and which it does. Once unsafe is used, no guarantee can be fully trusted. But the direction we're going with "integrity by default" (https://openjdk.org/jeps/8305968 https://openjdk.org/jeps/8305968) is that the application will need to acknowledge and approve the use of unsafe code by libraries, and so the author of the application could choose to more closely inspect the unsafe code and try to determine its blast radius.
- freecodyx 3y ago
  If we are using mmap and unsafe, then better use c
- papercrane 3y ago
  All the sub-2 second ones are. There is an impressive 3.2s solution that uses neither AOT or Unsafe. It's using the in-preview foreign memory and vector operations APIs. Browsing the solutions it looks like that the Unsafe solutions are winning because Unsafe lets them bypass bounds checks. The current fastest safe version: https://github.com/gunnarmorling/1brc/blob/main/src/main/java/dev/morling/onebrc/CalculateAverage_merykitty.java https://github.com/gunnarmorling/1brc/blob/main/src/main/jav...
  - anonymoushn 3y ago
    It's sort of wild that there's no vector load or store that doesn't include bounds checks. Even if you make a MemorySegment from 0 to 2^63-1 (~2^15 times larger than addressable memory on x64!) you'll pay for bounds checks on every load and every store.
    - pron 3y ago
      Only for random access. The compiler will hoist bounds checks out of more regularly-accessed loops (when the inlining is right). In fact, given that the top safe result was very close to the top unsafe result (especially considering the standard deviation), it looks like you need to write truly exceptional code to feel the cost of the random-access bounds checks. So it doesn't seem wild at all that the default is to give everyone safety at the expense of a performance cost that will only be felt by very few (and who can then enable unsafe code if they feel they need that last extra boost).
      - anonymoushn 3y ago
        Bounds checks in a MemorySegment that contains the whole addressable range 2^15 times provide no safety. Obviously. You've posted that users can use unsafe to avoid the bounds checks, but you're posting specifically about methods provided for MemorySegment that have no equivalent for Unsafe, so you're just incorrect. "Only for random access" is probably also incorrect. We could maybe have a look at the codegen for any of the top openjdk submissions which currently perform sequential access but increment the read pointer by ctz(movemask(eq(*ptr, c)))+k at each step. It's trivial for a person to prove that the bounds checks are redundant with the loop termination condition given the MemorySegment's length and given that ctz is at most 64, but it seems unlikely that the runtime manages it. It is of course also trivial for a person who knows that the MemorySegment is so large that it only disallows addresses that differ from allowed addresses by up to two bits not used for addressing to prove that all possible addresses are allowed, or at least that they address memory which is allowed to be accessed by a different address if the user masks off the high two bits first.
- vincnetas 3y ago
  3.2 seconds for fastest safe solution. So not bat i'd say.
- hocuspocus 3y ago
  Not all and from what I remember the top ranking hasn't changed that much since everyone started to update their solution with unsafe/mmap, rather showing that the gain is fairly marginal.
  - anonymoushn 3y ago
    I think this instead shows that there are many other popular techniques that achieve much more pessimization than the best-case use of MemorySegment over Unsafe or read over mmap.

dbacar 3y ago

..and all solutions use unsafe

borissk 3y ago
So it's better to write this sort of code in a language that's unsafe by default (e.g. C), rather than try to abuse Java. Reminds me of the code that Microsoft produced when they were trying to prove their new .NET Core is one of the fastest web runtimes - it was quite fast, but had nothing to do with the way C# code is written out there.
- coldpie 3y ago
  > So it's better to write this sort of code in a language that's unsafe by default (e.g. C), rather than try to abuse Java. I'm not necessarily disagreeing, but can you elaborate on why it's better? Using unsafe for some parts of the code doesn't throw out safety guarantees about all of the rest of the code.
  - anonymoushn 3y ago
    In this case it's better because C users have access to vector intrinsics that are much cheaper than the ones Java users have access to.
  - pron 3y ago
    > Using unsafe for some parts of the code doesn't throw out safety guarantees about all of the rest of the code. That's actually hard to prove because you don't know which guarantees the unsafe code can break; being unsafe, it could potentially, say, mutate arbitrary final fields of any object in the program. So while such code doesn't necessarily break invariants, there's no easy way to tell whether and which it does. Once unsafe is used, no guarantee can be fully trusted. But the direction we're going with "integrity by default" (https://openjdk.org/jeps/8305968 https://openjdk.org/jeps/8305968) is that the application will need to acknowledge and approve the use of unsafe code by libraries, and so the author of the application could choose to more closely inspect the unsafe code and try to determine its blast radius.
freecodyx 3y ago
If we are using mmap and unsafe, then better use c
papercrane 3y ago
All the sub-2 second ones are. There is an impressive 3.2s solution that uses neither AOT or Unsafe. It's using the in-preview foreign memory and vector operations APIs. Browsing the solutions it looks like that the Unsafe solutions are winning because Unsafe lets them bypass bounds checks. The current fastest safe version: https://github.com/gunnarmorling/1brc/blob/main/src/main/java/dev/morling/onebrc/CalculateAverage_merykitty.java https://github.com/gunnarmorling/1brc/blob/main/src/main/jav...
- anonymoushn 3y ago
  It's sort of wild that there's no vector load or store that doesn't include bounds checks. Even if you make a MemorySegment from 0 to 2^63-1 (~2^15 times larger than addressable memory on x64!) you'll pay for bounds checks on every load and every store.
  - pron 3y ago
    Only for random access. The compiler will hoist bounds checks out of more regularly-accessed loops (when the inlining is right). In fact, given that the top safe result was very close to the top unsafe result (especially considering the standard deviation), it looks like you need to write truly exceptional code to feel the cost of the random-access bounds checks. So it doesn't seem wild at all that the default is to give everyone safety at the expense of a performance cost that will only be felt by very few (and who can then enable unsafe code if they feel they need that last extra boost).
    - anonymoushn 3y ago
      Bounds checks in a MemorySegment that contains the whole addressable range 2^15 times provide no safety. Obviously. You've posted that users can use unsafe to avoid the bounds checks, but you're posting specifically about methods provided for MemorySegment that have no equivalent for Unsafe, so you're just incorrect. "Only for random access" is probably also incorrect. We could maybe have a look at the codegen for any of the top openjdk submissions which currently perform sequential access but increment the read pointer by ctz(movemask(eq(*ptr, c)))+k at each step. It's trivial for a person to prove that the bounds checks are redundant with the loop termination condition given the MemorySegment's length and given that ctz is at most 64, but it seems unlikely that the runtime manages it. It is of course also trivial for a person who knows that the MemorySegment is so large that it only disallows addresses that differ from allowed addresses by up to two bits not used for addressing to prove that all possible addresses are allowed, or at least that they address memory which is allowed to be accessed by a different address if the user masks off the high two bits first.
vincnetas 3y ago
3.2 seconds for fastest safe solution. So not bat i'd say.
hocuspocus 3y ago
Not all and from what I remember the top ranking hasn't changed that much since everyone started to update their solution with unsafe/mmap, rather showing that the gain is fairly marginal.
- anonymoushn 3y ago
  I think this instead shows that there are many other popular techniques that achieve much more pessimization than the best-case use of MemorySegment over Unsafe or read over mmap.