5 ms·

The most interesting aspect of this from my perspective was the importance of structs in C#. Java doesn't have this construct, making it harder to solve these

by moomin 15y ago

The most interesting aspect of this from my perspective was the importance of structs in C#. Java doesn't have this construct, making it harder to solve these problems in-memory.

barrkel 15y ago
You can simulate it with a bunch of parallel arrays, one array for each field of the "struct". Wrapping up such a construct in a flyweight object (I described this in a comment to the blog post) can then get much of the ease of use back (though you can't override operator== in Java).
- RodgerTheGreat 15y ago
  This is a good point, but I'd wager parallel arrays are slower because the components of a "struct" don't have spatial locality in memory- thus you have poor cache coherence. Of course, this isn't an issue if you're primarily passing the flyweight objects around and not accessing all the fields.
  - beagle3 15y ago
    > I'd wager parallel arrays are slower because the components of a "struct" don't have spatial locality in memory How much would you wager? I'm willing to take your money :) > Of course, this isn't an issue if you're primarily passing the flyweight objects around and not accessing all the fields. If you examine codebases, you see that this is actually the prevalent use case for objects in general. It turns out that in practice, parallel arrays are often significantly faster, because more often than not you _do_ access a lot of (memory consecutive) records, and you _don't_ access all the fields. Assume e.g. your structure has student names and numeric grades. For display purposes, you are likely to read both name and grade. However, for just about every other purpose, you are likely to scan/process grades without ever looking at the name (e.g., to compute grade statistics; or to sort by grade). And in this case, you actually have much _better_ cache locality than you would have otherwise -- and also much better memory usage compared to individual allocation of objects. Furthermore, if you take this approach, you find that your functions become type-concrete but use-generic, reducing your code footprint (both LOC and I-cache), because e.g. instead of "calcAverageGrade(student[] x)", you can just use a routine called "calcAverage(float[] x)", and call it ont he grade vector. APL, J and K take this approach to its logical conclusion. The result is programs that are 10-1000 times shorter than the idiomatically comparable Python, Java, C#, C++ etc., and that have runtimes the compare favorably with C and C++.
    - dpark 15y ago
      > It turns out that in practice, parallel arrays are often significantly faster, because more often than not you _do_ access a lot of (memory consecutive) records, and you _don't_ access all the fields. This doesn't hold if you're doing random access (which it sounds like they are, given that they're passing around lists of indices). In the random-access scenario, parallel arrays will require roughly O(M) times as many trips to main memory as the struct array, where M is the number of fields accessed.
      - beagle3 15y ago
        O(L/M) times as many trips, where L is the <average cache line size> divided by <average field size>. With 64 byte cache lines and 8 byte fields, this is at most 8, even if you have 200 fields in your object. In my experience, when I was still doubting this myself, I was unable to ever measure more than 20% slowdown on the least favorable (for columnar storage) workload, and I was able to measure about 200% speedup on a favorable workload. Note that even if they do pass around a list of indices, accesses are often (in practice) batched - because records that arrived together tend to be needed together. And the indices are often sorted (because of how they were generated, or because they are easy to sort) which then produces a very predictable access pattern for memory and disk. We can theorize about probable and improbable access patterns until tomorrow. My experience, and everyone that used column-major order that I'm aware of, is that in practice it almost always wins against row-major ("common") ordering, whether on disk or in memory. The fastest databases around (kdb+, vertica) use column major order. That should tell you something (about disk, but also about memory)
        dpark 15y ago
        > O(L/M) times as many trips Sorry, I'm really confused. Is this supposed to be "O(M/L)"? The note about clumped records is valid. That is often the case. Without knowing more about their workload, it's difficult to say whether they have that behavior, but it's quite likely. As for the fastest DBs, they use column order for a number of reasons. The big thing is that their access patterns are rarely random. They're optimized for scanning on keys. DBs like Fastbit can be extremely fast for whole-table scans. They aren't so fast if you need to find a specific entry. For maximum speed there, you need a dedicated index, and then it doesn't really matter whether the data is stored row-major or column-major.
robfig 15y ago
What is the distinction between struct and a class with all public members?
- msbarnett 15y ago
  Structs are value types in C#, there's no separate memory overhead for the reference to them.
- maximilianburke 15y ago
  As with C++, structs in C# can have private members. The big difference between structs and classes, though, is that structs are value types. This means that, for example, function local usage of struct instances can forego allocating them on the heap and instead allocate them in the program's activation records (stack frames). Because of the semantic differnces you can't just go switching all your classes to structs and realize a significant performance difference. Code like this: class Foo { int bar; } public static void Func(Foo[] arrayOfFoos) { Foo f = arrayOfFoos[0]; f.bar = 10; } will break in subtle ways because you are no longer manipulating the heap allocated instance via a reference but rather a copy that was allocated local to the function. Arrays of structs also have better cache locality which can improve performance on number crunching workloads and can also make it easier to exchange data between managed code and native code through a P/Invoke interface.

by moomin 15y ago

The most interesting aspect of this from my perspective was the importance of structs in C#. Java doesn't have this construct, making it harder to solve these problems in-memory.

barrkel 15y ago

You can simulate it with a bunch of parallel arrays, one array for each field of the "struct". Wrapping up such a construct in a flyweight object (I described this in a comment to the blog post) can then get much of the ease of use back (though you can't override operator== in Java).

RodgerTheGreat 15y ago
This is a good point, but I'd wager parallel arrays are slower because the components of a "struct" don't have spatial locality in memory- thus you have poor cache coherence. Of course, this isn't an issue if you're primarily passing the flyweight objects around and not accessing all the fields.
- beagle3 15y ago
  > I'd wager parallel arrays are slower because the components of a "struct" don't have spatial locality in memory How much would you wager? I'm willing to take your money :) > Of course, this isn't an issue if you're primarily passing the flyweight objects around and not accessing all the fields. If you examine codebases, you see that this is actually the prevalent use case for objects in general. It turns out that in practice, parallel arrays are often significantly faster, because more often than not you _do_ access a lot of (memory consecutive) records, and you _don't_ access all the fields. Assume e.g. your structure has student names and numeric grades. For display purposes, you are likely to read both name and grade. However, for just about every other purpose, you are likely to scan/process grades without ever looking at the name (e.g., to compute grade statistics; or to sort by grade). And in this case, you actually have much _better_ cache locality than you would have otherwise -- and also much better memory usage compared to individual allocation of objects. Furthermore, if you take this approach, you find that your functions become type-concrete but use-generic, reducing your code footprint (both LOC and I-cache), because e.g. instead of "calcAverageGrade(student[] x)", you can just use a routine called "calcAverage(float[] x)", and call it ont he grade vector. APL, J and K take this approach to its logical conclusion. The result is programs that are 10-1000 times shorter than the idiomatically comparable Python, Java, C#, C++ etc., and that have runtimes the compare favorably with C and C++.
  - dpark 15y ago
    > It turns out that in practice, parallel arrays are often significantly faster, because more often than not you _do_ access a lot of (memory consecutive) records, and you _don't_ access all the fields. This doesn't hold if you're doing random access (which it sounds like they are, given that they're passing around lists of indices). In the random-access scenario, parallel arrays will require roughly O(M) times as many trips to main memory as the struct array, where M is the number of fields accessed.
    - beagle3 15y ago
      O(L/M) times as many trips, where L is the <average cache line size> divided by <average field size>. With 64 byte cache lines and 8 byte fields, this is at most 8, even if you have 200 fields in your object. In my experience, when I was still doubting this myself, I was unable to ever measure more than 20% slowdown on the least favorable (for columnar storage) workload, and I was able to measure about 200% speedup on a favorable workload. Note that even if they do pass around a list of indices, accesses are often (in practice) batched - because records that arrived together tend to be needed together. And the indices are often sorted (because of how they were generated, or because they are easy to sort) which then produces a very predictable access pattern for memory and disk. We can theorize about probable and improbable access patterns until tomorrow. My experience, and everyone that used column-major order that I'm aware of, is that in practice it almost always wins against row-major ("common") ordering, whether on disk or in memory. The fastest databases around (kdb+, vertica) use column major order. That should tell you something (about disk, but also about memory)
      - dpark 15y ago
        > O(L/M) times as many trips Sorry, I'm really confused. Is this supposed to be "O(M/L)"? The note about clumped records is valid. That is often the case. Without knowing more about their workload, it's difficult to say whether they have that behavior, but it's quite likely. As for the fastest DBs, they use column order for a number of reasons. The big thing is that their access patterns are rarely random. They're optimized for scanning on keys. DBs like Fastbit can be extremely fast for whole-table scans. They aren't so fast if you need to find a specific entry. For maximum speed there, you need a dedicated index, and then it doesn't really matter whether the data is stored row-major or column-major.

robfig 15y ago

What is the distinction between struct and a class with all public members?

msbarnett 15y ago
Structs are value types in C#, there's no separate memory overhead for the reference to them.
maximilianburke 15y ago
As with C++, structs in C# can have private members. The big difference between structs and classes, though, is that structs are value types. This means that, for example, function local usage of struct instances can forego allocating them on the heap and instead allocate them in the program's activation records (stack frames). Because of the semantic differnces you can't just go switching all your classes to structs and realize a significant performance difference. Code like this: class Foo { int bar; } public static void Func(Foo[] arrayOfFoos) { Foo f = arrayOfFoos[0]; f.bar = 10; } will break in subtle ways because you are no longer manipulating the heap allocated instance via a reference but rather a copy that was allocated local to the function. Arrays of structs also have better cache locality which can improve performance on number crunching workloads and can also make it easier to exchange data between managed code and native code through a P/Invoke interface.