From Newsgroup: comp.programming

[Cross-post to comp.programming, Followup-To: comp.programming]

In article <11a6a6h$37i1n$[email protected]>,
Terje Mathisen <[email protected]> wrote:

Dan Cross wrote:

In article <11a5lqo$2v5bq$[email protected]>,
Terje Mathisen <[email protected]> wrote:

Not unrolling, the code is here:

https://godbolt.org/z/YnY5G1K49

The interesting part starts at line 28/29 .LBB0_02 in the asm window
where you can see (starting at line 37) a bunch of cmp r8,rsi / jae
<panic> sequences.

So you're not actually indexing into an _array_ here, but rather
into a _slice_, which is always bounds-checked in safe Rust
code.

My old asm/C brain _knows_ that a slice of something with a known
address and total length is effectively the same thing as an unmutable >array.

Sadly, though, it's not. :-/

Even if it isn't, the fact that I start by verifying that the slice
extends at least 7 bytes past the p index means that all of p,
p+1,p+2...p+6 must be valid, right?

One would think!

I do wonder, though, whether you'd get better object code using
`input.iter().chunks(n)` or `.windows(n)`.

I guess I can try this, I'm guessing chunks(7) will error out if less
than 7 elements are available?

But really what you want is to find all subsequences matching
the regular expression , `mul([0-9]+,[0-9]+)`, and then extract
the two numeric fields, multiple them, and sum the results.
That's a reduction over a sequence of products, which is itself
a reduction over a sequence of patches that yield pairs of
integers.

Yes, doing it that way is easy!

Well, I mean as a conceptual thing; not necessary using a regex
library. That is, mentally write the patterns down as a DFA and
then write that out as code+state tables.

[snip]
represent the input data. Nothing says it's not UTF-8, and from
what I understand, the guy who runs it usually isn't a jerk
about that kind of thing. I haven't tried to benchmark your
code against, e.g., this:

What you implement here is just Part1: After solving that you get to
read Part2 where you have to also detect "do()" and "don't()" sequences,
so that the multiplication result only adds to the part2 result if we're
not following a don't().

Ah. Yeah, I'm going to refrain; it's cool that folks are excited
about that, but it's not my favorite biscuit.

[snip]
I suspect yours may be somewhat faster, though this likely does
more error checking. YMMV.

My guess is that your code (after adding the simultaneous scans for the >do/don't markers) will take about twice as long (or more?) as the 7 us
both my own and u/maneatingape (reddit handle of the guy with the
fastest Rust solutions to all the 500+ puzzles) needs to deliver the result.

Maybe? I dunno; the library is probably optimized to use pretty
efficient algorithms, and/or simd and all that jazz.

[snip]
Setting up a combined Boyer-Moore would be doable:

If the fourth byte is '(', ')' or "'", check the preceeding bytes, if
not a match use a pre-computed skip table (maybe even one for each
initial match?) to increment the pointer. Hmmm... maybe I'll try this!

Right. This lets you potentially go sub-linear looking for the
tokens you care about. I wonder how it would stack up against
using something like `memchr::memmem`, though, since that'll get
you hardware acceleration using SIMD instructions and goofy
stuff like that.

- Dan C.

--- Synchronet 3.22a-Linux NewsLink 1.2

From Newsgroup: comp.programming

Dan Cross wrote:

[Cross-post to comp.programming, Followup-To: comp.programming]

In article <11a6a6h$37i1n$[email protected]>,
Terje Mathisen <[email protected]> wrote:

Dan Cross wrote:

In article <11a5lqo$2v5bq$[email protected]>,
Terje Mathisen <[email protected]> wrote:

Not unrolling, the code is here:

https://godbolt.org/z/YnY5G1K49

The interesting part starts at line 28/29 .LBB0_02 in the asm window
where you can see (starting at line 37) a bunch of cmp r8,rsi / jae
<panic> sequences.

So you're not actually indexing into an _array_ here, but rather
into a _slice_, which is always bounds-checked in safe Rust
code.

My old asm/C brain _knows_ that a slice of something with a known
address and total length is effectively the same thing as an unmutable
array.

Sadly, though, it's not. :-/

Even if it isn't, the fact that I start by verifying that the slice
extends at least 7 bytes past the p index means that all of p,
p+1,p+2...p+6 must be valid, right?

One would think!

I do wonder, though, whether you'd get better object code using
`input.iter().chunks(n)` or `.windows(n)`.

I guess I can try this, I'm guessing chunks(7) will error out if less
than 7 elements are available?

But really what you want is to find all subsequences matching
the regular expression , `mul([0-9]+,[0-9]+)`, and then extract
the two numeric fields, multiple them, and sum the results.
That's a reduction over a sequence of products, which is itself
a reduction over a sequence of patches that yield pairs of
integers.

Yes, doing it that way is easy!

Well, I mean as a conceptual thing; not necessary using a regex
library. That is, mentally write the patterns down as a DFA and
then write that out as code+state tables.

[snip]
represent the input data. Nothing says it's not UTF-8, and from
what I understand, the guy who runs it usually isn't a jerk
about that kind of thing. I haven't tried to benchmark your
code against, e.g., this:

What you implement here is just Part1: After solving that you get to
read Part2 where you have to also detect "do()" and "don't()" sequences,
so that the multiplication result only adds to the part2 result if we're
not following a don't().

Ah. Yeah, I'm going to refrain; it's cool that folks are excited
about that, but it's not my favorite biscuit.

[snip]
I suspect yours may be somewhat faster, though this likely does
more error checking. YMMV.

My guess is that your code (after adding the simultaneous scans for the
do/don't markers) will take about twice as long (or more?) as the 7 us
both my own and u/maneatingape (reddit handle of the guy with the
fastest Rust solutions to all the 500+ puzzles) needs to deliver the result.

Maybe? I dunno; the library is probably optimized to use pretty
efficient algorithms, and/or simd and all that jazz.

[snip]
Setting up a combined Boyer-Moore would be doable:

If the fourth byte is '(', ')' or "'", check the preceeding bytes, if
not a match use a pre-computed skip table (maybe even one for each
initial match?) to increment the pointer. Hmmm... maybe I'll try this!

Right. This lets you potentially go sub-linear looking for the
tokens you care about. I wonder how it would stack up against
using something like `memchr::memmem`, though, since that'll get
you hardware acceleration using SIMD instructions and goofy
stuff like that.

We're already well past that point!

The current bunch of optimization freaks employs portable SIMD anywhere
it results in even small speedups.

For the current setup, the main issue is that is so relatively small
that any kind of significant setup overhead mans that you lose out in
the end. The combined BM could be mostly precompiled instead of runtime
skip table geneation overhead.

Terje
--
- <Terje.Mathisen at tmsw.no>
"almost all programming can be viewed as an exercise in caching"
--- Synchronet 3.22a-Linux NewsLink 1.2

From Newsgroup: comp.programming

In article <11aau1v$sbtb$[email protected]>,
Terje Mathisen <[email protected]> wrote:

Dan Cross wrote:

[snip]
Right. This lets you potentially go sub-linear looking for the
tokens you care about. I wonder how it would stack up against
using something like `memchr::memmem`, though, since that'll get
you hardware acceleration using SIMD instructions and goofy
stuff like that.

We're already well past that point!

The current bunch of optimization freaks employs portable SIMD anywhere
it results in even small speedups.

For the current setup, the main issue is that is so relatively small
that any kind of significant setup overhead mans that you lose out in
the end. The combined BM could be mostly precompiled instead of runtime
skip table geneation overhead.

Yeah, I'd think that if you wanted to use BM you'd be able to
pre-compute the skip tables by hand and just write them out as
constants at compile-time.

Sounds like the folks who are into this are deep into the weeds
already; if it's fun for you then rock on. I wish you luck!

- Dan C.

--- Synchronet 3.22a-Linux NewsLink 1.2