undefined | Better HN

0 pointsjiggawatts4y ago0 comments

Please elaborate on that bug. The rust function I provided replaces "select, *" correctly with "select, _". Is that not what it was supposed to do? I checked that it works with empty arrays, arrays with one entry, etc...

Thinking about it, this version boils down the logic to its barest essence:

    fn test(input: &mut [&str]) {
    
        let mut was_select = false;
        for i in input.iter_mut() {
            if was_select && *i == "*" { *i = "_"; was_select = false; }
            else { was_select = *i == "select"; }
        }
    }

It runs in 5.5 nanoseconds per iteration, which is just absurdly fast. That's about 200x faster than your K version!

What I like about this Rust version is that it reflects the approach that for a computer processor is optimal, yet it is high-level and readable. I could convert that "test" function easily enough to a generic "replace" function similar to a string search & replace, but one that can operate on any mutable iterator with the maximum possible efficiency, not just arrays.

Then, your K code that requires "careful reading" to slowly tease apart the meaning could be converted to a form that is practically prose:

    let mut input = ["select", "*", "bar", "potato"];
    replace( &mut input, &["select", "*"], &["select", "_"] );*

0 comments

geocar4y ago

> The rust function I provided replaces "select, *" correctly with "select, _". Is that not what it was supposed to do?

No. It is not supposed to modify its input but return a copy.

jiggawattsOP4y ago

Granted, if replacing arbitrary sequences with arbitrary sequences, then copying is necessary, as this could result in the output length increasing.

However, for replacing scalars only, the in-place mutable version is in some sense superior: it doesn't force a memory allocation. Moreover it can be trivially converted into a copying version by simply wrapping it in a function that first copies the input, and then mutates it in-place. The reverse is not true: the copying version cannot be wrapped to create a non-allocating version.

To be honest, I wish more languages put this kind of effort into their standard libraries, but most have about 10% of what I would like to see. For example, this kind of "string matching" is really "sequence matching" and ought to be fully generic for any underlying comparable and copyable type, not just arrays of characters. String search algorithms like Boyer-Moore ought to be directly applicable to arrays of integers or enums, e.g.: for recognition of code patterns in lists of parsed tokens.

At least one person has done something like this for Rust: https://github.com/peterjoel/rust-iter-replace/blob/6c575eeb...

Similarly, there's the new InPlaceIterable, which is interesting but not quite enough to suit my taste: https://doc.rust-lang.org/std/iter/trait.InPlaceIterable.htm...

geocar4y ago

> However, for replacing scalars only, the in-place mutable version is in some sense superior

I mean, we are talking about someone else's code and someone else's decisions. If we can change the rules, you're absolutely right we can do much much better.

But beware microbenchmarking too much: Giving the treatment you gave your rust to your entire program can be more than exhausting, it can actually end you up with a slower program simply because your program gets too big!

k makes a lot of compromises to stay small enough to keep both the interpreter and the application in L1, but whole-program speeds benefit from this treatment sometimes by factors of 1000x or more, and that's hard to show with these microbenchmarks as well.

> To be honest, I wish more languages put this kind of effort into their standard libraries, but most have about 10% of what I would like to see. For example, this kind of "string matching" is really "sequence matching" and ought to be fully generic for any underlying comparable and copyable type, not just arrays of characters

In APL, this is called ⍷ (pronounced "find") and sometimes even APL-ers momentarily forget it exists[1], but in k you always have to make it yourself, usually (as we did today) with ⍸ (where) and ≡ (match), but sometimes some other way[2], and this works on all the different data types k supports (including integers, enums, dates, times, symbols) and across multiple cores as well. You are right to predict it would be useful: It is useful :)

[1]: https://news.ycombinator.com/item?id=27229994

[2]: https://news.ycombinator.com/item?id=16851862

j / k navigate · click thread line to collapse

0 pointsjiggawatts4y ago0 comments

Thinking about it, this version boils down the logic to its barest essence:

    fn test(input: &mut [&str]) {
    
        let mut was_select = false;
        for i in input.iter_mut() {
            if was_select && *i == "*" { *i = "_"; was_select = false; }
            else { was_select = *i == "select"; }
        }
    }

It runs in 5.5 nanoseconds per iteration, which is just absurdly fast. That's about 200x faster than your K version!

Then, your K code that requires "careful reading" to slowly tease apart the meaning could be converted to a form that is practically prose:

    let mut input = ["select", "*", "bar", "potato"];
    replace( &mut input, &["select", "*"], &["select", "_"] );*

0 comments

geocar4y ago

> The rust function I provided replaces "select, *" correctly with "select, _". Is that not what it was supposed to do?

No. It is not supposed to modify its input but return a copy.

jiggawattsOP4y ago

Granted, if replacing arbitrary sequences with arbitrary sequences, then copying is necessary, as this could result in the output length increasing.

At least one person has done something like this for Rust: https://github.com/peterjoel/rust-iter-replace/blob/6c575eeb...

Similarly, there's the new InPlaceIterable, which is interesting but not quite enough to suit my taste: https://doc.rust-lang.org/std/iter/trait.InPlaceIterable.htm...

geocar4y ago

> However, for replacing scalars only, the in-place mutable version is in some sense superior

I mean, we are talking about someone else's code and someone else's decisions. If we can change the rules, you're absolutely right we can do much much better.

[1]: https://news.ycombinator.com/item?id=27229994

[2]: https://news.ycombinator.com/item?id=16851862

j / k navigate · click thread line to collapse