Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.programming > #16933 > unrolled thread

Re: Optimization by programmers

Back to article view | Back to comp.programming

This discussion starts older than the indexed window; earlier articles aren't shown. The article labeled Started by below is the oldest one visible, not the original post.

Contents

  Re: Optimization by programmers cross@spitfire.i.gajendra.net (Dan Cross) - 2026-10-08 21:28 +0000
    Re: Optimization by programmers Terje Mathisen <terje.mathisen@tmsw.no> - 2026-10-09 16:34 +0200
      Re: Optimization by programmers cross@spitfire.i.gajendra.net (Dan Cross) - 2026-10-09 14:38 +0000

#16933 — Re: Optimization by programmers

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

In article <11a6a6h$37i1n$1@dont-email.me>,
Terje Mathisen  <terje.mathisen@tmsw.no> wrote:
>Dan Cross wrote:
>> In article <11a5lqo$2v5bq$1@dont-email.me>,
>> Terje Mathisen  <terje.mathisen@tmsw.no> 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.

[toc] | [next] | [standalone]

#16934

Dan Cross wrote:
> [Cross-post to comp.programming, Followup-To: comp.programming]
> 
> In article <11a6a6h$37i1n$1@dont-email.me>,
> Terje Mathisen  <terje.mathisen@tmsw.no> wrote:
>> Dan Cross wrote:
>>> In article <11a5lqo$2v5bq$1@dont-email.me>,
>>> Terje Mathisen  <terje.mathisen@tmsw.no> 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"

[toc] | [prev] | [next] | [standalone]

#16935

In article <11aau1v$sbtb$1@dont-email.me>,
Terje Mathisen  <terje.mathisen@tmsw.no> 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.

[toc] | [prev] | [standalone]

Back to top | Article view | comp.programming

csiph-web