3 ms·

Sure, you're right about safety and conciseness. But C/C++ implementations maintain fidelity to the complexity analyses found in the algorithm literature. Amor

by sn41 6y ago

Sure, you're right about safety and conciseness. But C/C++ implementations maintain fidelity to the complexity analyses found in the algorithm literature. Amortized analysis in Okasaki-style OCaml implementations does not really compare to amortized analysis in lazy languages like Haskell, and all of these are quite different from the regular pointer-based implementations. I think perhaps the real safe alternative might be Rust.

lmm 6y ago
> But C/C++ implementations maintain fidelity to the complexity analyses found in the algorithm literature. Not in any meaningful sense. On modern hardware, the dominant factor affecting performance is cache efficiency, and that's not at all visible in C/C++ code. So you're not really any better off in C/C++ than you are in OCaml (to use your example): the asymptotics are valid, but you have no idea (without resorting to reasoning about compiler and CPU internals) when a small change is going to cause aliasing or blow out the cache and lead to an order of magnitude performance difference.
- AnimalMuppet 6y ago
  But at least in C/C++ you can fix it. That is, I can control how my data lines up with the cache in C/C++, with sufficient care and effort. Doing the same thing in Haskell or OCaml would be considerably harder.
  - lmm 6y ago
    > That is, I can control how my data lines up with the cache in C/C++, with sufficient care and effort. Doing the same thing in Haskell or OCaml would be considerably harder. Would it really? The OCaml compiler is pretty simple and consistent; there was a story here not so long ago where some OCaml users diagnosed a CPU bug that people using C/C++ hadn't noticed.
    - kragen 6y ago
      I don't know if the problem is that you don't know OCaml or that you don't know C, but yes, it is considerably harder; in OCaml you cannot embed objects in other objects as you can in C (and C++, and Golang), because OCaml uses the Lisp memory model, as described in http://canonical.org/~kragen/memory-models http://canonical.org/~kragen/memory-models. Consequently you end up with things which are perhaps conceptually a single object potentially strewn around the heap at random, however the allocator and the garbage collector choose to arrange them, and linked together by pointers. There's a lot of payoff for this — it's safe and trivially easy to write parametrically polymorphic code in OCaml, while it ranges from fiddly and error-prone to overwhelming to impossible in different languages in the C family — but it's a major fundamental difference, and it does have some runtime efficiency costs.

by sn41 6y ago

lmm 6y ago

> But C/C++ implementations maintain fidelity to the complexity analyses found in the algorithm literature. Not in any meaningful sense. On modern hardware, the dominant factor affecting performance is cache efficiency, and that's not at all visible in C/C++ code. So you're not really any better off in C/C++ than you are in OCaml (to use your example): the asymptotics are valid, but you have no idea (without resorting to reasoning about compiler and CPU internals) when a small change is going to cause aliasing or blow out the cache and lead to an order of magnitude performance difference.

AnimalMuppet 6y ago
But at least in C/C++ you can fix it. That is, I can control how my data lines up with the cache in C/C++, with sufficient care and effort. Doing the same thing in Haskell or OCaml would be considerably harder.
- lmm 6y ago
  > That is, I can control how my data lines up with the cache in C/C++, with sufficient care and effort. Doing the same thing in Haskell or OCaml would be considerably harder. Would it really? The OCaml compiler is pretty simple and consistent; there was a story here not so long ago where some OCaml users diagnosed a CPU bug that people using C/C++ hadn't noticed.
  - kragen 6y ago
    I don't know if the problem is that you don't know OCaml or that you don't know C, but yes, it is considerably harder; in OCaml you cannot embed objects in other objects as you can in C (and C++, and Golang), because OCaml uses the Lisp memory model, as described in http://canonical.org/~kragen/memory-models http://canonical.org/~kragen/memory-models. Consequently you end up with things which are perhaps conceptually a single object potentially strewn around the heap at random, however the allocator and the garbage collector choose to arrange them, and linked together by pointers. There's a lot of payoff for this — it's safe and trivially easy to write parametrically polymorphic code in OCaml, while it ranges from fiddly and error-prone to overwhelming to impossible in different languages in the C family — but it's a major fundamental difference, and it does have some runtime efficiency costs.