5 ms·

It seems almost as if it'd be more useful to not explicitly expose operators as applicable to arrays, but implement SIMD optimization for operator expressions i

by slver 5y ago

It seems almost as if it'd be more useful to not explicitly expose operators as applicable to arrays, but implement SIMD optimization for operator expressions in .map(function) and something like .binaryMap(right, function) ex. [1, 2, 3].binaryMap([10, 10, 10], (a, b) => a * b) // Produces [10, 20, 30] This would be easier to optimize when compiled because the expressions can be simplified and mapped to the right SIMD instructions.

klibertp 5y ago
Unfortunately, I have no idea about the implementation and what optimizations are done in J or APL for which operations :( I know that there are hardcoded "fast path" expressions (particular combinations of operations) which have much better performance than more general expressions doing the same thing, so it might be that the optimization happens at that level. OTOH, your example is very verbose when compared to J's version: 1 2 3 * 10 10 20 30 Plus, in J it generalizes to higher dimensional arrays: i. 3 3 0 1 2 3 4 5 6 7 8 (1 + i. 3 3) * 10 10 20 30 40 50 60 70 80 90
- slver 5y ago
  My example is verbose in order to clearly communicate the principle. I can trivially shorten it to [1, 2, 3].map(a => a * 10) if I wanted to literally carry out that task alone. [[0, 1, 2], [3, 4, 5], [6, 7, 8]].flatMap(a => a * 10)
  - klibertp 5y ago
    I think this is pseudo-code? `flatMap` and `=>` for lambdas look like Scala, but there are no array literals using `[]` there. Assuming you mean Scala-like semantics, your second example wouldn't work at all: scala> Array(Array(1,2), Array(4,5)).flatMap(a => a * 10) ^ error: value * is not a member of Array[Int] You would need to write it like this: scala> Array(Array(1,2), Array(4,5)).flatMap(a => a.map(x => x * 10)) But then you'd get a flattened array of ints, not array of arrays of ints: res6: Array[Int] = Array(10, 20, 40, 50) So to get the same result as (i. 2 2) * 10 You'd need to write: scala> Array(Array(1,2), Array(4,5)).map(a => a.map(x => x * 10)) res7: Array[Array[Int]] = Array(Array(10, 20), Array(40, 50)) ...which is more verbose, no? :) EDIT: obviously, I mean "map in map" part, not the Array initialization! The problem with list comprehensions and `map`, `filter` and friends is that they work very well for flat lists, or lists of lists in some specific circumstances (ie. when you can use `flatMap`). 2D arrays in the general case, and arrays with higher dimensions are really hard to work with using these primitives, unless you have some clever overloads, like what Clojure does. I think Haskell also has a solution for this, but I don't know it enough to comment further, unfortunately :)
    - slver 5y ago
      What I can't understand is what would J do if I tell it to sum these two arrays: 1 2 3 4 5 6 7 8 I.e. 5 elements and 3 elements
      - klibertp 5y ago
        1 2 3 + 4 5 6 7 |length error | 1 2 3 +4 5 6 7 In general - depends on the operation. Sometimes the verb checks that both operands have the same rank and dimensions, sometimes the shorter/smaller side gets applied column-wise (or cell-wise/page-wise): (2 2 $ 1 2 3 4) NB. $ means "reshape" 1 2 3 4 (2 2 $ 1 2 3 4) + 1 2 2 3 5 6 Sometimes the shorter side is repeated as much as needed to get the correct length, and sometimes the shorter side gets extended with 0s, and sometimes the longer side gets truncated: (2 2 $ 1 2 3 4 5 6) 1 2 3 4 (2 4 $ 1 2 3 4 5 6) 1 2 3 4 5 6 1 2 To be perfectly honest: it's very unintuitive to me and I have to check the docs pretty often to see how the given verb behaves outside of the simplest case (ie. when the rank and dimensions match). But, I learned J as a hobby and never invested enough time into it to really learn all the built-ins, nor did I try using J outside of toy examples, so maybe this behavior becomes convenient once you internalized it? EDIT: forgot to mention, you can also control the effective rank of the verb, like this: <"0 (2 2 $ 1 2 3 4) ┌─┬─┐ │1│2│ ├─┼─┤ │3│4│ └─┴─┘ <"1 (2 2 $ 1 2 3 4) ┌───┬───┐ │1 2│3 4│ └───┴───┘ <"2 (2 2 $ 1 2 3 4) ┌───┐ │1 2│ │3 4│ └───┘ the `<` verb means "box", without the `"n` part you'd get the last value, which is a 1-dimensional array of boxes of length 1 (with 2x2 array inside the box). By selecting rank of the verb, you can decide on which level the verb should be applied: with `"0` it's applied to the smallest possible chunks of the array (cells - you get 2x2 array of boxes), with `"1` you apply the verb to bigger chunks (rows), and so on, for input arrays of any dimensions (so if you have a 3x2x2 array, `"2` will apply the verb to the 3 2x2 arrays).
        slver 5y ago
        Gotta say, "depends on the operation" was the most unfortunate possible answer to my question, alas :-) Maybe one day we'll figure out how to make a consistent array language ;-)
- rscho 5y ago
  even less verbose: (>: i. 3 3) * 10
  - rscho 5y ago
    ...or 10 * >: i. 3 3 FWIW
dzaima 5y ago
That just removes a tiny tiny bit of dynamic dispatch overhead. Which is still needed anyways, as array languages can often dynamically switch between 1-bit, 8-bit, 16-bit, 32-bit integer (and 64-bit float) arrays, depending on the elements, completely transparently to the user.
- slver 5y ago
  Most compilers can inline statically defined closures in these contexts. And tracing JITs do this even when the closure is not define statically (but is stable). It's more about allowing the SIMD goodness without the ambiguity and restrictions of "scalar operators work on arrays" implemented naively.
  - rscho 5y ago
    Traditional array languages (APL,J) are not amenable to static compilation due to other dynamic issues, though. I think Dyalog APL is experimenting with a bytecode interpreter, but no JITs in sight either (that I know of). The very dynamic aspect of those languages makes that difficult. I'd love a compileable similar language, though. To replace R/Python for statistics that are sooooo annoying when exploring data due to verbosity.
    - rklmno 5y ago
      That's not really the issue. It's certainly true that, depending on how the code is written, you may not be able to optimize out the language implementation from the compiled program. But that just turns into a link against a library with support for the language for your hypothetical compiled program. That said, the compiler being hypothetical is a very real obstacle. But even there the problem is not that the language can't be compiled -- it's that no one has bothered to implement a compiler for it. Anyways, if you throw in some ML type inference, and some tools for characterizing the resulting code and its interfaces, you can generate code from an array language which is quite similar to the code you would get from a variety of other languages.
  - klibertp 5y ago

by slver 5y ago

klibertp 5y ago

Unfortunately, I have no idea about the implementation and what optimizations are done in J or APL for which operations :( I know that there are hardcoded "fast path" expressions (particular combinations of operations) which have much better performance than more general expressions doing the same thing, so it might be that the optimization happens at that level. OTOH, your example is very verbose when compared to J's version: 1 2 3 * 10 10 20 30 Plus, in J it generalizes to higher dimensional arrays: i. 3 3 0 1 2 3 4 5 6 7 8 (1 + i. 3 3) * 10 10 20 30 40 50 60 70 80 90

slver 5y ago
My example is verbose in order to clearly communicate the principle. I can trivially shorten it to [1, 2, 3].map(a => a * 10) if I wanted to literally carry out that task alone. [[0, 1, 2], [3, 4, 5], [6, 7, 8]].flatMap(a => a * 10)
- klibertp 5y ago
  I think this is pseudo-code? `flatMap` and `=>` for lambdas look like Scala, but there are no array literals using `[]` there. Assuming you mean Scala-like semantics, your second example wouldn't work at all: scala> Array(Array(1,2), Array(4,5)).flatMap(a => a * 10) ^ error: value * is not a member of Array[Int] You would need to write it like this: scala> Array(Array(1,2), Array(4,5)).flatMap(a => a.map(x => x * 10)) But then you'd get a flattened array of ints, not array of arrays of ints: res6: Array[Int] = Array(10, 20, 40, 50) So to get the same result as (i. 2 2) * 10 You'd need to write: scala> Array(Array(1,2), Array(4,5)).map(a => a.map(x => x * 10)) res7: Array[Array[Int]] = Array(Array(10, 20), Array(40, 50)) ...which is more verbose, no? :) EDIT: obviously, I mean "map in map" part, not the Array initialization! The problem with list comprehensions and `map`, `filter` and friends is that they work very well for flat lists, or lists of lists in some specific circumstances (ie. when you can use `flatMap`). 2D arrays in the general case, and arrays with higher dimensions are really hard to work with using these primitives, unless you have some clever overloads, like what Clojure does. I think Haskell also has a solution for this, but I don't know it enough to comment further, unfortunately :)
  - slver 5y ago
    What I can't understand is what would J do if I tell it to sum these two arrays: 1 2 3 4 5 6 7 8 I.e. 5 elements and 3 elements
    - klibertp 5y ago
      1 2 3 + 4 5 6 7 |length error | 1 2 3 +4 5 6 7 In general - depends on the operation. Sometimes the verb checks that both operands have the same rank and dimensions, sometimes the shorter/smaller side gets applied column-wise (or cell-wise/page-wise): (2 2 $ 1 2 3 4) NB. $ means "reshape" 1 2 3 4 (2 2 $ 1 2 3 4) + 1 2 2 3 5 6 Sometimes the shorter side is repeated as much as needed to get the correct length, and sometimes the shorter side gets extended with 0s, and sometimes the longer side gets truncated: (2 2 $ 1 2 3 4 5 6) 1 2 3 4 (2 4 $ 1 2 3 4 5 6) 1 2 3 4 5 6 1 2 To be perfectly honest: it's very unintuitive to me and I have to check the docs pretty often to see how the given verb behaves outside of the simplest case (ie. when the rank and dimensions match). But, I learned J as a hobby and never invested enough time into it to really learn all the built-ins, nor did I try using J outside of toy examples, so maybe this behavior becomes convenient once you internalized it? EDIT: forgot to mention, you can also control the effective rank of the verb, like this: <"0 (2 2 $ 1 2 3 4) ┌─┬─┐ │1│2│ ├─┼─┤ │3│4│ └─┴─┘ <"1 (2 2 $ 1 2 3 4) ┌───┬───┐ │1 2│3 4│ └───┴───┘ <"2 (2 2 $ 1 2 3 4) ┌───┐ │1 2│ │3 4│ └───┘ the `<` verb means "box", without the `"n` part you'd get the last value, which is a 1-dimensional array of boxes of length 1 (with 2x2 array inside the box). By selecting rank of the verb, you can decide on which level the verb should be applied: with `"0` it's applied to the smallest possible chunks of the array (cells - you get 2x2 array of boxes), with `"1` you apply the verb to bigger chunks (rows), and so on, for input arrays of any dimensions (so if you have a 3x2x2 array, `"2` will apply the verb to the 3 2x2 arrays).
      - slver 5y ago
        Gotta say, "depends on the operation" was the most unfortunate possible answer to my question, alas :-) Maybe one day we'll figure out how to make a consistent array language ;-)
rscho 5y ago
even less verbose: (>: i. 3 3) * 10
- rscho 5y ago
  ...or 10 * >: i. 3 3 FWIW

dzaima 5y ago

That just removes a tiny tiny bit of dynamic dispatch overhead. Which is still needed anyways, as array languages can often dynamically switch between 1-bit, 8-bit, 16-bit, 32-bit integer (and 64-bit float) arrays, depending on the elements, completely transparently to the user.

slver 5y ago
Most compilers can inline statically defined closures in these contexts. And tracing JITs do this even when the closure is not define statically (but is stable). It's more about allowing the SIMD goodness without the ambiguity and restrictions of "scalar operators work on arrays" implemented naively.
- rscho 5y ago
  Traditional array languages (APL,J) are not amenable to static compilation due to other dynamic issues, though. I think Dyalog APL is experimenting with a bytecode interpreter, but no JITs in sight either (that I know of). The very dynamic aspect of those languages makes that difficult. I'd love a compileable similar language, though. To replace R/Python for statistics that are sooooo annoying when exploring data due to verbosity.
  - rklmno 5y ago
    That's not really the issue. It's certainly true that, depending on how the code is written, you may not be able to optimize out the language implementation from the compiled program. But that just turns into a link against a library with support for the language for your hypothetical compiled program. That said, the compiler being hypothetical is a very real obstacle. But even there the problem is not that the language can't be compiled -- it's that no one has bothered to implement a compiler for it. Anyways, if you throw in some ML type inference, and some tools for characterizing the resulting code and its interfaces, you can generate code from an array language which is quite similar to the code you would get from a variety of other languages.
- klibertp 5y ago