8 ms·

I'm getting the impression that our problems with caching are related to the way we abstract computer memory. If languages are built with the assumption that yo

by d33 11y ago

I'm getting the impression that our problems with caching are related to the way we abstract computer memory. If languages are built with the assumption that you can jump around your RAM with no cost, I guess that can result in code that could have been made more efficient. This makes me wonder - what kind of abstraction would help alleviate this problem?

hacker_9 11y ago
More abstractions! Higher level languages!
- rawnlq 11y ago
  Don't you need a lower level language (than even assembly and maybe even some sort of hardware support)? Virtual memory abstracts away whether the address is in RAM or disk. Going a step further, you need to undo even one more layer of abstraction so you know whether you're accessing L1, L2, or main memory. But to be honest I think just malloc is a decent abstraction. You control memory layout and the rest is having algorithms with good access patterns.
pkaye 11y ago
But jumping around in DRAM does have a slower access time.
BenoitP 11y ago
Great question. I'm a huge fan of separating the business specifications from talking about the execution. ------- Some runtimes will do this under the hood. RDBMS execution plans are a good example. Plan costs are calculated using data-dependent statistics. And cache-friendliness is taken into account: in postgres, hash joins are made to fit L1 (tuples per bucket = 10) and L3 caches (work_mem default to 4MB, after which batches are introduced) [1] Some JITs will also monitor performance and behavior, and try to speculatively prune unused paths. But this is all letting the runtime deal with it. ------- Execution should be treated as an orthogonal but tweakable concern. And be exposed in some way to the user. Halide [2] is one very interesting approach, is letting user choose: * between materialization and compute-again * parallelism levels * chunk sizes * scheduling, etc. However the storage is implied by the execution chosen. Which to me is a constraint that is automatically enforced, and not exposed. ------- All knobs, and their consequences, should be readily available to both users and compilers. To me, typed languages could, should contain so much more information about performance (or anything!). The perfect abstraction should be the seamless integration of 4 languages: * Logical business requirements (what you want done). Should be user friendly * Business properties requirements (constraints like liveness, performance envelope, security, or business ones). Declarative * A language to help in proofs. Think TLA+[3] or the checker framework [4]. * A language to express which implementations are chosen, knobs to configure, how the layout is done (array of structs, struct of arrays?). Think Halide or JAI [5]. Such a combination of languages should be built on extremely typed primitives; the combination of which should propagate type information, and provide hooks to provide more type information. An implementation of a sum of a value over a range should make emerge information about: * which business properties it offers * which items will benefit from fitting in cache * which parts can be stopped without lock contention * different options for the memory layout coming into and out of this algorithm In the internals, something as simple as a + b would look like: @Associative @Commutative @MapsTo(Algebra.addition) @Inlineable @CanSafePointBefore @WillNotContend @NonBlocking @CacheSizefunction(argumentsSize + returnSize) @BatchingStrategies(Single,Batch.L1Size,Batch.L1Size) @WaitOnIOStrategy(Unscheduleable) @ArgumentPassing(ref,value,ArrayOfStruct,StructOfArrays) @ReturnPassing(ref,value,Array) @Properties(case unsigned: ret >= a and ret >= b) def plus( a @NumberType(uint16, int, IEEEfloat, double, @CustomizeableNumber) , b @NumberType(uint16, int, IEEEfloat, double, @CustomizeableNumber) ) { return @ a + @Impl(asm_x86_add,simd_x86_add,cuda_add) @NumberTypeInference b } ------- In short: a language into which anyone can commit type information, with type information that could inform performance. [1] http://patshaughnessy.net/2016/1/22/is-your-postgres-query-starved-for-memory http://patshaughnessy.net/2016/1/22/is-your-postgres-query-s... [2] http://halide-lang.org/ http://halide-lang.org/ [3] http://cseweb.ucsd.edu/~daricket/papers/fm2012.pdf http://cseweb.ucsd.edu/~daricket/papers/fm2012.pdf [4] http://types.cs.washington.edu/checker-framework/current/checker-framework-manual.html http://types.cs.washington.edu/checker-framework/current/che... [5] https://inductive.no/jai/ https://inductive.no/jai/
fpoling 11y ago
The point of this article is that typical code that deals with persistent/immutable data structures can be optimized to work efficiently in presence of cache hierarchy. That is, with persistent data structures one can keep code rather abstract while still allowing for cache friendly implementation.

by d33 11y ago

hacker_9 11y ago

More abstractions! Higher level languages!

rawnlq 11y ago
Don't you need a lower level language (than even assembly and maybe even some sort of hardware support)? Virtual memory abstracts away whether the address is in RAM or disk. Going a step further, you need to undo even one more layer of abstraction so you know whether you're accessing L1, L2, or main memory. But to be honest I think just malloc is a decent abstraction. You control memory layout and the rest is having algorithms with good access patterns.

pkaye 11y ago

But jumping around in DRAM does have a slower access time.

BenoitP 11y ago

Great question. I'm a huge fan of separating the business specifications from talking about the execution. ------- Some runtimes will do this under the hood. RDBMS execution plans are a good example. Plan costs are calculated using data-dependent statistics. And cache-friendliness is taken into account: in postgres, hash joins are made to fit L1 (tuples per bucket = 10) and L3 caches (work_mem default to 4MB, after which batches are introduced) [1] Some JITs will also monitor performance and behavior, and try to speculatively prune unused paths. But this is all letting the runtime deal with it. ------- Execution should be treated as an orthogonal but tweakable concern. And be exposed in some way to the user. Halide [2] is one very interesting approach, is letting user choose: * between materialization and compute-again * parallelism levels * chunk sizes * scheduling, etc. However the storage is implied by the execution chosen. Which to me is a constraint that is automatically enforced, and not exposed. ------- All knobs, and their consequences, should be readily available to both users and compilers. To me, typed languages could, should contain so much more information about performance (or anything!). The perfect abstraction should be the seamless integration of 4 languages: * Logical business requirements (what you want done). Should be user friendly * Business properties requirements (constraints like liveness, performance envelope, security, or business ones). Declarative * A language to help in proofs. Think TLA+[3] or the checker framework [4]. * A language to express which implementations are chosen, knobs to configure, how the layout is done (array of structs, struct of arrays?). Think Halide or JAI [5]. Such a combination of languages should be built on extremely typed primitives; the combination of which should propagate type information, and provide hooks to provide more type information. An implementation of a sum of a value over a range should make emerge information about: * which business properties it offers * which items will benefit from fitting in cache * which parts can be stopped without lock contention * different options for the memory layout coming into and out of this algorithm In the internals, something as simple as a + b would look like: @Associative @Commutative @MapsTo(Algebra.addition) @Inlineable @CanSafePointBefore @WillNotContend @NonBlocking @CacheSizefunction(argumentsSize + returnSize) @BatchingStrategies(Single,Batch.L1Size,Batch.L1Size) @WaitOnIOStrategy(Unscheduleable) @ArgumentPassing(ref,value,ArrayOfStruct,StructOfArrays) @ReturnPassing(ref,value,Array) @Properties(case unsigned: ret >= a and ret >= b) def plus( a @NumberType(uint16, int, IEEEfloat, double, @CustomizeableNumber) , b @NumberType(uint16, int, IEEEfloat, double, @CustomizeableNumber) ) { return @ a + @Impl(asm_x86_add,simd_x86_add,cuda_add) @NumberTypeInference b } ------- In short: a language into which anyone can commit type information, with type information that could inform performance. [1] http://patshaughnessy.net/2016/1/22/is-your-postgres-query-starved-for-memory http://patshaughnessy.net/2016/1/22/is-your-postgres-query-s... [2] http://halide-lang.org/ http://halide-lang.org/ [3] http://cseweb.ucsd.edu/~daricket/papers/fm2012.pdf http://cseweb.ucsd.edu/~daricket/papers/fm2012.pdf [4] http://types.cs.washington.edu/checker-framework/current/checker-framework-manual.html http://types.cs.washington.edu/checker-framework/current/che... [5] https://inductive.no/jai/ https://inductive.no/jai/

fpoling 11y ago

The point of this article is that typical code that deals with persistent/immutable data structures can be optimized to work efficiently in presence of cache hierarchy. That is, with persistent data structures one can keep code rather abstract while still allowing for cache friendly implementation.