6 ms·

So reverse a list/slice of anything else then?

by joppy 5y ago

deleted 5y ago
[deleted]
tialaramex 5y ago
Sure, reversing slices of say integers makes lots of sense, people definitely use that. I don't remember enough Go to know how tricky that is - presumably it is not a built-in feature? Rust's slices have reverse() but the implementation is a little hairier than you might expect: https://doc.rust-lang.org/src/core/slice/mod.rs.html#625 https://doc.rust-lang.org/src/core/slice/mod.rs.html#625 explains why, it wants to persuade LLVM that the things we're swapping are definitely different things, so it cuts the slice in half (if there's an odd middle element no matter, it needn't move anywhere by definition) and swaps between halves, so that LLVM can see OK, this necessarily is two different things, no aliasing is possible. I can't think an interviewer is expecting you to show that unless you're interviewing for a job working on optimisations in the compiler or something.
- morelisp 5y ago
  I'm really curious why LLVM can't figure out that a[i:j] and a[j:k] are disjoint without help. Is something about the use of Range making it opaque?
  - tialaramex 5y ago
    Mmm, I don't recognise your notation, are a[i:j] and a[j:k] really disjoint? Isn't a[j] in both of these slices?
    - morelisp 5y ago
      In all programming languages I know of using this syntax the upper bound is exclusive.
      - cbolton 5y ago
        It's inclusive in R, Julia, Matlab, Fortran and presumably most languages use 1-based indices by default.
        morelisp 5y ago
        Fair I guess - of those I only used Fortran and not in an environment which supported the colon syntax. (Once you've chosen the wrong way to address array elements of course you'll end up with the wrong way to denote bounds, to take the contrapositive of the classic Djikstra note.) But in this thread we're talking about Go - and the syntax is also used in Python and Ruby and with the same semantics `..` in Rust - and above all else the notation was clear from my question when I explicitly said those sets were disjoint - and that question is the much more interesting thing, I think?
        thetallstick 5y ago
        If i==j==k then they’re not disjoint.
        morelisp 5y ago
        Then they're both zero length and a zero-length set is disjoint from all other sets. Anyone want to explain why Rust needs to explicitly de-alias this yet? What a useless digression...
        tialaramex 5y ago
        Why LLVM needs this explaining? Probably somewhere an optimiser could inspect something and it doesn't. Rust cuts the slice in half and swaps between the halves, so probably LLVM doesn't convince itself that if you did those swaps directly they aren't ever aliased, but once there are two slices which can't overlap it can see it's fine.

So reverse a list/slice of anything else then?

by joppy 5y ago

So reverse a list/slice of anything else then?

deleted 5y ago

[deleted]

tialaramex 5y ago

Sure, reversing slices of say integers makes lots of sense, people definitely use that. I don't remember enough Go to know how tricky that is - presumably it is not a built-in feature? Rust's slices have reverse() but the implementation is a little hairier than you might expect: https://doc.rust-lang.org/src/core/slice/mod.rs.html#625 https://doc.rust-lang.org/src/core/slice/mod.rs.html#625 explains why, it wants to persuade LLVM that the things we're swapping are definitely different things, so it cuts the slice in half (if there's an odd middle element no matter, it needn't move anywhere by definition) and swaps between halves, so that LLVM can see OK, this necessarily is two different things, no aliasing is possible. I can't think an interviewer is expecting you to show that unless you're interviewing for a job working on optimisations in the compiler or something.

morelisp 5y ago
I'm really curious why LLVM can't figure out that a[i:j] and a[j:k] are disjoint without help. Is something about the use of Range making it opaque?
- tialaramex 5y ago
  Mmm, I don't recognise your notation, are a[i:j] and a[j:k] really disjoint? Isn't a[j] in both of these slices?
  - morelisp 5y ago
    In all programming languages I know of using this syntax the upper bound is exclusive.
    - cbolton 5y ago
      It's inclusive in R, Julia, Matlab, Fortran and presumably most languages use 1-based indices by default.
      - morelisp 5y ago
        Fair I guess - of those I only used Fortran and not in an environment which supported the colon syntax. (Once you've chosen the wrong way to address array elements of course you'll end up with the wrong way to denote bounds, to take the contrapositive of the classic Djikstra note.) But in this thread we're talking about Go - and the syntax is also used in Python and Ruby and with the same semantics `..` in Rust - and above all else the notation was clear from my question when I explicitly said those sets were disjoint - and that question is the much more interesting thing, I think?
        thetallstick 5y ago
        If i==j==k then they’re not disjoint.
        morelisp 5y ago
        Then they're both zero length and a zero-length set is disjoint from all other sets. Anyone want to explain why Rust needs to explicitly de-alias this yet? What a useless digression...
        tialaramex 5y ago
        Why LLVM needs this explaining? Probably somewhere an optimiser could inspect something and it doesn't. Rust cuts the slice in half and swaps between the halves, so probably LLVM doesn't convince itself that if you did those swaps directly they aren't ever aliased, but once there are two slices which can't overlap it can see it's fine.