4 ms·

> This is one example why your statement above is not true. You are misreading my comment. I’m not intentionally contradicting myself in two paragraphs next to

> This is one example why your statement above is not true. You are misreading my comment. I’m not intentionally contradicting myself in two paragraphs next to each other (I’m not always the brightest but still). The point is that contrary to what the article states ML developers are not avoiding mutations because they are uneasy to use but because they trust their compiler when they know it will do good. Proof is that in other case they will use mutations when it makes sense to do so because the compiler does not do a good job. The first paragraph refers to the specific case my comment quotes just before: data structure traversal and storage of elements in a set.

derdi 2y ago
> The point is that contrary to what the article states ML developers are not avoiding mutations because they are uneasy to use but because they trust their compiler when they know it will do good. Proof is that in other case they will use mutations when it makes sense to do so because the compiler does not do a good job. It will do a good job, yes. Will it do the best possible job compared to some other algorithm or data structure? It can't. Not in general. And maybe not in the specific case either: > The first paragraph refers to the specific case my comment quotes just before: data structure traversal and storage of elements in a set. So, this: https://ocaml.org/play#code=bW9kdWxlIE15X2R5bmFycmF5ID0gc3RydWN0CgogIHR5cGUgJ2EgdCA9IHsgbXV0YWJsZSBsZW5ndGg6IGludDsgbXV0YWJsZSB2YWx1ZXM6ICdhIGFycmF5IH0KCiAgbGV0IG1ha2UgaW5pdCA9CiAgICB7IGxlbmd0aCA9IDA7IHZhbHVlcyA9IEFycmF5Lm1ha2UgMTAgaW5pdCB9CgogIGxldCBhZGQgZCB4ID0KICAgIGlmIGQubGVuZ3RoID0gQXJyYXkubGVuZ3RoIGQudmFsdWVzIHRoZW4gYmVnaW4KICAgICAgZC52YWx1ZXMgPC0gQXJyYXkuKGFwcGVuZCBkLnZhbHVlcyAobWFrZSAobGVuZ3RoIGQudmFsdWVzKSB4KSkKICAgIGVuZDsKICAgIGQudmFsdWVzLihkLmxlbmd0aCkgPC0geDsKICAgIGQubGVuZ3RoIDwtIGQubGVuZ3RoICsgMQoKZW5kCgpsZXQgdGltZSBmbiA9CiAgbGV0IHN0YXJ0ID0gU3lzLnRpbWUgKCkgaW4KICBpZ25vcmUgKGZuICgpKTsKICBsZXQgZmluaXNoID0gU3lzLnRpbWUgKCkgaW4KICBmaW5pc2ggLS4gc3RhcnQKCmxldCBsaXN0X2JlbmNoIGlucHV0ID0KICBmb3IgaSA9IDEgdG8gMyBkbwogICAgbGV0IHQgPSB0aW1lIChmdW4gKCkgLT4gTGlzdC5tYXAgKGZ1biB4IC0%2BIHggKyAxKSBpbnB1dCkgaW4KICAgIEZvcm1hdC5wcmludGYgImxpc3Q6ICAgICAgICAlZiBzZWNcbiUhIiB0CiAgZG9uZQoKbGV0IGR5bmFycmF5X2JlbmNoIGlucHV0ID0KICBmb3IgaSA9IDEgdG8gMyBkbwogICAgbGV0IGQgPSBEeW5hcnJheS5jcmVhdGUgKCkgaW4KICAgIGxldCB0ID0gdGltZSAoZnVuICgpIC0%2BIExpc3QuaXRlciAoZnVuIHggLT4gRHluYXJyYXkuYWRkX2xhc3QgZCAoeCArIDEpKSBpbnB1dCkgaW4KICAgIEZvcm1hdC5wcmludGYgImR5bmFycmF5OiAgICAlZiBzZWNcbiUhIiB0CiAgZG9uZQoKbGV0IG15X2R5bmFycmF5X2JlbmNoIGlucHV0ID0KICBmb3IgaSA9IDEgdG8gMyBkbwogICAgbGV0IGQgPSBNeV9keW5hcnJheS5tYWtlICgtMSkgaW4KICAgIGxldCB0ID0gdGltZSAoZnVuICgpIC0%2BIExpc3QuaXRlciAoZnVuIHggLT4gTXlfZHluYXJyYXkuYWRkIGQgKHggKyAxKSkgaW5wdXQpIGluCiAgICBGb3JtYXQucHJpbnRmICJteSBkeW5hcnJheTogJWYgc2VjXG4lISIgdAogIGRvbmUKCmxldCBfID0KICBsZXQgaW5wdXQgPSBMaXN0LmluaXQgKGludF9vZl9zdHJpbmcgU3lzLmFyZ3YuKDIpKSBGdW4uaWQgaW4KICBtYXRjaCBTeXMuYXJndi4oMSkgd2l0aAogIHwgImxpc3QiIC0%2BIGxpc3RfYmVuY2ggaW5wdXQKICB8ICJkeW5hcnJheSIgLT4gZHluYXJyYXlfYmVuY2ggaW5wdXQKICB8ICJteV9keW5hcnJheSIgLT4gbXlfZHluYXJyYXlfYmVuY2ggaW5wdXQKICB8IF8gLT4gKCkK https://ocaml.org/play#code=bW9kdWxlIE15X2R5bmFycmF5ID0gc3Ry... $ for len in 5_000_000 10_000_000 25_000_000; do echo "-- ${len} elements --"; ./a.out list $len; ./a.out dynarray $len; ./a.out my_dynarray $len; echo; done -- 5_000_000 elements -- list: 0.191551 sec list: 0.196947 sec list: 0.192806 sec dynarray: 0.301362 sec dynarray: 0.268592 sec dynarray: 0.266118 sec my dynarray: 0.163004 sec my dynarray: 0.142986 sec my dynarray: 0.143634 sec -- 10_000_000 elements -- list: 0.377447 sec list: 0.367951 sec list: 0.312575 sec dynarray: 0.607158 sec dynarray: 0.582378 sec dynarray: 0.538621 sec my dynarray: 0.319705 sec my dynarray: 0.296607 sec my dynarray: 0.286634 sec -- 25_000_000 elements -- list: 0.971244 sec list: 0.953493 sec list: 0.922049 sec dynarray: 1.515892 sec dynarray: 1.319543 sec dynarray: 1.328461 sec my dynarray: 1.119322 sec my dynarray: 0.971288 sec my dynarray: 0.973556 sec -- 50_000_000 elements -- list: 1.852812 sec list: 1.848514 sec list: 1.505391 sec dynarray: 3.065143 sec dynarray: 2.941400 sec dynarray: 2.672760 sec my dynarray: 2.115499 sec my dynarray: 1.963535 sec my dynarray: 1.995470 sec -- 75_000_000 elements -- list: 2.942536 sec list: 2.910063 sec list: 2.354291 sec dynarray: 4.567284 sec dynarray: 4.342670 sec dynarray: 3.979809 sec my dynarray: 2.528073 sec my dynarray: 2.225738 sec my dynarray: 2.226844 sec A simple dynamic array implementation (my_dynarray) beats a list over a wide range of lengths. But not at all lengths! OCaml's built-in Dynarray is not competitive, but that's because it wants to make certain strong guarantees. To be clear, I agree with your general point that we can do just fine writing nice clean pure functional OCaml code for most of our code and can hand-optimize where needed. But your very specific claims rub me the wrong way.
- derdi 2y ago
  Oops, this had a performance bug. Instead of: if d.length = Array.length d.values then begin d.values <- Array.(append d.values (make (length d.values) x)) end; the array reallocation should actually be: if d.length = Array.length d.values then begin let new_array = Array.make (Array.length d.values * 2) x in Array.blit d.values 0 new_array 0 (Array.length d.values); d.values <- new_array end; otherwise we allocate about a third more memory than needed. It's telling that even with this performance bug the dynamic array was broadly better than lists. New results for the previously slowest cases: -- 25_000_000 elements -- list: 0.977002 sec list: 0.963903 sec list: 0.950473 sec dynarray: 1.476165 sec dynarray: 1.281724 sec dynarray: 1.343222 sec my dynarray: 0.872558 sec my dynarray: 0.755902 sec my dynarray: 0.753746 sec -- 50_000_000 elements -- list: 1.914777 sec list: 1.886989 sec list: 1.542614 sec dynarray: 2.922376 sec dynarray: 2.783559 sec dynarray: 2.537473 sec my dynarray: 1.725873 sec my dynarray: 1.545252 sec my dynarray: 1.515591 sec -- 75_000_000 elements -- list: 2.827154 sec list: 2.835789 sec list: 2.318733 sec dynarray: 4.354404 sec dynarray: 4.150271 sec dynarray: 3.781488 sec my dynarray: 1.887360 sec my dynarray: 1.929286 sec my dynarray: 1.814873 sec This turns an uneasy head-to-head into a clear win for dynamic arrays. Honestly, how could it be otherwise?
  - brabel 2y ago
    But they are still very much in the same order of magnitude... pretty impressive that these solutions are all in the same ballpark, I would've expected much bigger differences.
    - derdi 2y ago
      The dynamic array spends most of its time copying old elements as it grows exponentially. If you pre-size it to the right size, you eliminate this copying, and the difference becomes 5x. In practice you often have an idea of the size, at least as a rough estimation, so you would win by a larger margin. But that was not part of the spec. Also, other ways of organizing dynamic not-quite-an-array-but-not-quite-a-linked-list data structures exist. It could be a dynamic array (or linked list) of dynamic arrays to eliminate repeated copying of the oldest elements.

derdi 2y ago

> The point is that contrary to what the article states ML developers are not avoiding mutations because they are uneasy to use but because they trust their compiler when they know it will do good. Proof is that in other case they will use mutations when it makes sense to do so because the compiler does not do a good job. It will do a good job, yes. Will it do the best possible job compared to some other algorithm or data structure? It can't. Not in general. And maybe not in the specific case either: > The first paragraph refers to the specific case my comment quotes just before: data structure traversal and storage of elements in a set. So, this: https://ocaml.org/play#code=bW9kdWxlIE15X2R5bmFycmF5ID0gc3RydWN0CgogIHR5cGUgJ2EgdCA9IHsgbXV0YWJsZSBsZW5ndGg6IGludDsgbXV0YWJsZSB2YWx1ZXM6ICdhIGFycmF5IH0KCiAgbGV0IG1ha2UgaW5pdCA9CiAgICB7IGxlbmd0aCA9IDA7IHZhbHVlcyA9IEFycmF5Lm1ha2UgMTAgaW5pdCB9CgogIGxldCBhZGQgZCB4ID0KICAgIGlmIGQubGVuZ3RoID0gQXJyYXkubGVuZ3RoIGQudmFsdWVzIHRoZW4gYmVnaW4KICAgICAgZC52YWx1ZXMgPC0gQXJyYXkuKGFwcGVuZCBkLnZhbHVlcyAobWFrZSAobGVuZ3RoIGQudmFsdWVzKSB4KSkKICAgIGVuZDsKICAgIGQudmFsdWVzLihkLmxlbmd0aCkgPC0geDsKICAgIGQubGVuZ3RoIDwtIGQubGVuZ3RoICsgMQoKZW5kCgpsZXQgdGltZSBmbiA9CiAgbGV0IHN0YXJ0ID0gU3lzLnRpbWUgKCkgaW4KICBpZ25vcmUgKGZuICgpKTsKICBsZXQgZmluaXNoID0gU3lzLnRpbWUgKCkgaW4KICBmaW5pc2ggLS4gc3RhcnQKCmxldCBsaXN0X2JlbmNoIGlucHV0ID0KICBmb3IgaSA9IDEgdG8gMyBkbwogICAgbGV0IHQgPSB0aW1lIChmdW4gKCkgLT4gTGlzdC5tYXAgKGZ1biB4IC0%2BIHggKyAxKSBpbnB1dCkgaW4KICAgIEZvcm1hdC5wcmludGYgImxpc3Q6ICAgICAgICAlZiBzZWNcbiUhIiB0CiAgZG9uZQoKbGV0IGR5bmFycmF5X2JlbmNoIGlucHV0ID0KICBmb3IgaSA9IDEgdG8gMyBkbwogICAgbGV0IGQgPSBEeW5hcnJheS5jcmVhdGUgKCkgaW4KICAgIGxldCB0ID0gdGltZSAoZnVuICgpIC0%2BIExpc3QuaXRlciAoZnVuIHggLT4gRHluYXJyYXkuYWRkX2xhc3QgZCAoeCArIDEpKSBpbnB1dCkgaW4KICAgIEZvcm1hdC5wcmludGYgImR5bmFycmF5OiAgICAlZiBzZWNcbiUhIiB0CiAgZG9uZQoKbGV0IG15X2R5bmFycmF5X2JlbmNoIGlucHV0ID0KICBmb3IgaSA9IDEgdG8gMyBkbwogICAgbGV0IGQgPSBNeV9keW5hcnJheS5tYWtlICgtMSkgaW4KICAgIGxldCB0ID0gdGltZSAoZnVuICgpIC0%2BIExpc3QuaXRlciAoZnVuIHggLT4gTXlfZHluYXJyYXkuYWRkIGQgKHggKyAxKSkgaW5wdXQpIGluCiAgICBGb3JtYXQucHJpbnRmICJteSBkeW5hcnJheTogJWYgc2VjXG4lISIgdAogIGRvbmUKCmxldCBfID0KICBsZXQgaW5wdXQgPSBMaXN0LmluaXQgKGludF9vZl9zdHJpbmcgU3lzLmFyZ3YuKDIpKSBGdW4uaWQgaW4KICBtYXRjaCBTeXMuYXJndi4oMSkgd2l0aAogIHwgImxpc3QiIC0%2BIGxpc3RfYmVuY2ggaW5wdXQKICB8ICJkeW5hcnJheSIgLT4gZHluYXJyYXlfYmVuY2ggaW5wdXQKICB8ICJteV9keW5hcnJheSIgLT4gbXlfZHluYXJyYXlfYmVuY2ggaW5wdXQKICB8IF8gLT4gKCkK https://ocaml.org/play#code=bW9kdWxlIE15X2R5bmFycmF5ID0gc3Ry... $ for len in 5_000_000 10_000_000 25_000_000; do echo "-- ${len} elements --"; ./a.out list $len; ./a.out dynarray $len; ./a.out my_dynarray $len; echo; done -- 5_000_000 elements -- list: 0.191551 sec list: 0.196947 sec list: 0.192806 sec dynarray: 0.301362 sec dynarray: 0.268592 sec dynarray: 0.266118 sec my dynarray: 0.163004 sec my dynarray: 0.142986 sec my dynarray: 0.143634 sec -- 10_000_000 elements -- list: 0.377447 sec list: 0.367951 sec list: 0.312575 sec dynarray: 0.607158 sec dynarray: 0.582378 sec dynarray: 0.538621 sec my dynarray: 0.319705 sec my dynarray: 0.296607 sec my dynarray: 0.286634 sec -- 25_000_000 elements -- list: 0.971244 sec list: 0.953493 sec list: 0.922049 sec dynarray: 1.515892 sec dynarray: 1.319543 sec dynarray: 1.328461 sec my dynarray: 1.119322 sec my dynarray: 0.971288 sec my dynarray: 0.973556 sec -- 50_000_000 elements -- list: 1.852812 sec list: 1.848514 sec list: 1.505391 sec dynarray: 3.065143 sec dynarray: 2.941400 sec dynarray: 2.672760 sec my dynarray: 2.115499 sec my dynarray: 1.963535 sec my dynarray: 1.995470 sec -- 75_000_000 elements -- list: 2.942536 sec list: 2.910063 sec list: 2.354291 sec dynarray: 4.567284 sec dynarray: 4.342670 sec dynarray: 3.979809 sec my dynarray: 2.528073 sec my dynarray: 2.225738 sec my dynarray: 2.226844 sec A simple dynamic array implementation (my_dynarray) beats a list over a wide range of lengths. But not at all lengths! OCaml's built-in Dynarray is not competitive, but that's because it wants to make certain strong guarantees. To be clear, I agree with your general point that we can do just fine writing nice clean pure functional OCaml code for most of our code and can hand-optimize where needed. But your very specific claims rub me the wrong way.

derdi 2y ago
Oops, this had a performance bug. Instead of: if d.length = Array.length d.values then begin d.values <- Array.(append d.values (make (length d.values) x)) end; the array reallocation should actually be: if d.length = Array.length d.values then begin let new_array = Array.make (Array.length d.values * 2) x in Array.blit d.values 0 new_array 0 (Array.length d.values); d.values <- new_array end; otherwise we allocate about a third more memory than needed. It's telling that even with this performance bug the dynamic array was broadly better than lists. New results for the previously slowest cases: -- 25_000_000 elements -- list: 0.977002 sec list: 0.963903 sec list: 0.950473 sec dynarray: 1.476165 sec dynarray: 1.281724 sec dynarray: 1.343222 sec my dynarray: 0.872558 sec my dynarray: 0.755902 sec my dynarray: 0.753746 sec -- 50_000_000 elements -- list: 1.914777 sec list: 1.886989 sec list: 1.542614 sec dynarray: 2.922376 sec dynarray: 2.783559 sec dynarray: 2.537473 sec my dynarray: 1.725873 sec my dynarray: 1.545252 sec my dynarray: 1.515591 sec -- 75_000_000 elements -- list: 2.827154 sec list: 2.835789 sec list: 2.318733 sec dynarray: 4.354404 sec dynarray: 4.150271 sec dynarray: 3.781488 sec my dynarray: 1.887360 sec my dynarray: 1.929286 sec my dynarray: 1.814873 sec This turns an uneasy head-to-head into a clear win for dynamic arrays. Honestly, how could it be otherwise?
- brabel 2y ago
  But they are still very much in the same order of magnitude... pretty impressive that these solutions are all in the same ballpark, I would've expected much bigger differences.
  - derdi 2y ago
    The dynamic array spends most of its time copying old elements as it grows exponentially. If you pre-size it to the right size, you eliminate this copying, and the difference becomes 5x. In practice you often have an idea of the size, at least as a rough estimation, so you would win by a larger margin. But that was not part of the spec. Also, other ways of organizing dynamic not-quite-an-array-but-not-quite-a-linked-list data structures exist. It could be a dynamic array (or linked list) of dynamic arrays to eliminate repeated copying of the oldest elements.