4 ms·

For contex, Ross Ihaka is one of the original authors of R. This date back to 2008. Also see Ross Ihaka's 2010 paper: https://www.stat.auckland.ac.nz/~ihaka/dow

by widdma 9y ago

For contex, Ross Ihaka is one of the original authors of R. This date back to 2008. Also see Ross Ihaka's 2010 paper: https://www.stat.auckland.ac.nz/~ihaka/downloads/JSM-2010.pdf https://www.stat.auckland.ac.nz/~ihaka/downloads/JSM-2010.pd...

simonbyrne 9y ago
Thanks, I had seen the original link before, but not this. As a Julia developer, I like that his 5 lessons are ones that Julia has successfully addressed. In particular: 1. Julia had the benefit of clever design, as well as not needing to support legacy interfaces that are difficult to optimise. Python has had similar problems (which needs to support all the different low-level interfaces), whereas JavaScript, which provides fewer ways to "mess with the internals", now has several high-performance engines. 4. Although Julia does provide the ability for type annotation, it is actually rather rarely necessary, due again to good language design which makes automatic type inference feasible. 5. Julia originally discouraged use of vectorised operations for this reason. But now we've gone the other way, with special "dot" syntax which avoids allocating intermediate arrays. See https://julialang.org/blog/2017/01/moredots https://julialang.org/blog/2017/01/moredots for more details.
- JadeNB 9y ago
  As a Julia developer, and for the benefit of someone (me!) who doesn't know anything about such matters, are you in a position to respond to ScottBurson's post (https://news.ycombinator.com/item?id=14801186 https://news.ycombinator.com/item?id=14801186) on efficient collections with functional semantics?
  - micro2588 9y ago
    Julia has been designed for single core performance fullstop. Functional collections may work well with a state of the art GC, with Julia's not so much. The fact that Julia can interop seemlessly with C code (easily) kind of bounds the design of the GC. I think it is a little disingenuous to say that a Julia programmer does not have to worry about types. Type inference alleviates many burdens, but correct typing of arguments is essential (and hidden promotions or casting can kill performance). So while you can write correct programs easily, for efficient programs you end up worrying about this quite a lot.
    - ScottBurson 9y ago
      > Functional collections may work well with a state of the art GC, with Julia's not so much. I don't know the specifics of Julia's GC, but this seems a strange thing to say in 2017. Douglas Crosher's conservative generational collector for CMUCL (also used in SBCL AFAIK) supports C interoperation and is entirely adequate for handling the extra garbage that (admittedly) is generated when using functional collections. I don't recall exactly when he wrote that collector, but it must have been 20 years ago at least. It would be strange if Julia weren't using something at least as sophisticated.
    - simonbyrne 9y ago
      I'm not sure I understand: why would the C interop limit the design of the GC? I didn't say Julia programmers don't have to worry about types, my comment was only about type annotations, though they are obviously related. Perhaps a better way to phrase it is: by worrying a little bit about types, you can generally avoid the need for type annotations. Hopefully as the tooling around the language matures, we can reduce the amount of worrying required.
  - ScottBurson 9y ago
    No reply from Simon, but for the record, here's how I would do it. The Julia representation of a matrix would be a pair of an array and an override map, a functional map which is initially empty. Pointwise functional update returns a new matrix with a new value in one cell; the implementation returns a new pair of the same array and a new override map, computed as the previous override map functionally updated with the new mapping ((i, j) -> x). Pointwise access looks in the override map first, and if it finds no mapping there, looks in the array. When you want to perform a matrix operation, like multiplication, that for efficiency needs to operate on a plain array, here's what you do. First, if the override map is empty, you can use the array as it is. Otherwise, you make a new copy of the array, then iterate through the override map, storing each value in the array at the specified coordinates. Then you write the pointer to the copied and updated array into the array slot of the original pair. Yes, this modifies a nominally immutable object, but critically, it does so in a way that doesn't change its semantics. Finally you write, into the override-map slot of the original pair, a pointer to the canonical empty map. Now you can pass the array to your matrix multiply routine, or whatever. The two writes don't even require locking in a multithreaded situation, though on many architectures there will need to be a memory barrier instruction between them, so another thread can't read the two writes in the wrong order. Given that, the worst that can happen is that another thread sees the updated array but the original override map, whereupon it will make a redundant copy of the array and redundantly apply the updates to it, doing a little extra work but producing an identical array.
    - StefanKarpinski 9y ago
      This design seems workable for vectorized operations where the overhead of the override map can be amortized away (like matmul). The problem lies with scalar operations on individual array elements. Most high-level, dynamic languages don't bother themselves with those operations and instead encourage programmers only to use predefined, vectorized kernels. Julia isn't like that, however. A key property of the language is that you can write low-level C-style code with for/while loops, operating on individual array elements – and get C-like performance. The overhead of an overlaid structure like you describe becomes fatal in this situation since you pay for it with every element you touch. There may be clever compiler optimizations that can claw back some of that overhead – but one of the design principles of Julia is to avoid needing clever tricks in the first place. Instead, do the straightforward fast thing. In this case, that dictates standard C-style contiguous-memory mutable arrays – there's just nothing that can match their raw performance.
  - simonbyrne 9y ago
    I've replied now.

by widdma 9y ago

simonbyrne 9y ago

Thanks, I had seen the original link before, but not this. As a Julia developer, I like that his 5 lessons are ones that Julia has successfully addressed. In particular: 1. Julia had the benefit of clever design, as well as not needing to support legacy interfaces that are difficult to optimise. Python has had similar problems (which needs to support all the different low-level interfaces), whereas JavaScript, which provides fewer ways to "mess with the internals", now has several high-performance engines. 4. Although Julia does provide the ability for type annotation, it is actually rather rarely necessary, due again to good language design which makes automatic type inference feasible. 5. Julia originally discouraged use of vectorised operations for this reason. But now we've gone the other way, with special "dot" syntax which avoids allocating intermediate arrays. See https://julialang.org/blog/2017/01/moredots https://julialang.org/blog/2017/01/moredots for more details.

JadeNB 9y ago
As a Julia developer, and for the benefit of someone (me!) who doesn't know anything about such matters, are you in a position to respond to ScottBurson's post (https://news.ycombinator.com/item?id=14801186 https://news.ycombinator.com/item?id=14801186) on efficient collections with functional semantics?
- micro2588 9y ago
  Julia has been designed for single core performance fullstop. Functional collections may work well with a state of the art GC, with Julia's not so much. The fact that Julia can interop seemlessly with C code (easily) kind of bounds the design of the GC. I think it is a little disingenuous to say that a Julia programmer does not have to worry about types. Type inference alleviates many burdens, but correct typing of arguments is essential (and hidden promotions or casting can kill performance). So while you can write correct programs easily, for efficient programs you end up worrying about this quite a lot.
  - ScottBurson 9y ago
    > Functional collections may work well with a state of the art GC, with Julia's not so much. I don't know the specifics of Julia's GC, but this seems a strange thing to say in 2017. Douglas Crosher's conservative generational collector for CMUCL (also used in SBCL AFAIK) supports C interoperation and is entirely adequate for handling the extra garbage that (admittedly) is generated when using functional collections. I don't recall exactly when he wrote that collector, but it must have been 20 years ago at least. It would be strange if Julia weren't using something at least as sophisticated.
  - simonbyrne 9y ago
    I'm not sure I understand: why would the C interop limit the design of the GC? I didn't say Julia programmers don't have to worry about types, my comment was only about type annotations, though they are obviously related. Perhaps a better way to phrase it is: by worrying a little bit about types, you can generally avoid the need for type annotations. Hopefully as the tooling around the language matures, we can reduce the amount of worrying required.
- ScottBurson 9y ago
  No reply from Simon, but for the record, here's how I would do it. The Julia representation of a matrix would be a pair of an array and an override map, a functional map which is initially empty. Pointwise functional update returns a new matrix with a new value in one cell; the implementation returns a new pair of the same array and a new override map, computed as the previous override map functionally updated with the new mapping ((i, j) -> x). Pointwise access looks in the override map first, and if it finds no mapping there, looks in the array. When you want to perform a matrix operation, like multiplication, that for efficiency needs to operate on a plain array, here's what you do. First, if the override map is empty, you can use the array as it is. Otherwise, you make a new copy of the array, then iterate through the override map, storing each value in the array at the specified coordinates. Then you write the pointer to the copied and updated array into the array slot of the original pair. Yes, this modifies a nominally immutable object, but critically, it does so in a way that doesn't change its semantics. Finally you write, into the override-map slot of the original pair, a pointer to the canonical empty map. Now you can pass the array to your matrix multiply routine, or whatever. The two writes don't even require locking in a multithreaded situation, though on many architectures there will need to be a memory barrier instruction between them, so another thread can't read the two writes in the wrong order. Given that, the worst that can happen is that another thread sees the updated array but the original override map, whereupon it will make a redundant copy of the array and redundantly apply the updates to it, doing a little extra work but producing an identical array.
  - StefanKarpinski 9y ago
    This design seems workable for vectorized operations where the overhead of the override map can be amortized away (like matmul). The problem lies with scalar operations on individual array elements. Most high-level, dynamic languages don't bother themselves with those operations and instead encourage programmers only to use predefined, vectorized kernels. Julia isn't like that, however. A key property of the language is that you can write low-level C-style code with for/while loops, operating on individual array elements – and get C-like performance. The overhead of an overlaid structure like you describe becomes fatal in this situation since you pay for it with every element you touch. There may be clever compiler optimizations that can claw back some of that overhead – but one of the design principles of Julia is to avoid needing clever tricks in the first place. Instead, do the straightforward fast thing. In this case, that dictates standard C-style contiguous-memory mutable arrays – there's just nothing that can match their raw performance.
- simonbyrne 9y ago
  I've replied now.