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

Groups > comp.programming > #16933

Re: Optimization by programmers

Cross-posted to 2 groups.

Followups directed to: comp.programming

Show all headers | View raw

[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.

Back to comp.programming | Previous | Next — Next in thread | Find similar | Unroll thread

Thread

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

csiph-web