Path: csiph.com!weretis.net!feeder9.news.weretis.net!panix!.POSTED.spitfire.i.gajendra.net!not-for-mail From: cross@spitfire.i.gajendra.net (Dan Cross) Newsgroups: comp.programming,comp.arch Subject: Re: Optimization by programmers Followup-To: comp.programming Date: Thu, 8 Oct 2026 21:28:55 -0000 (UTC) Organization: PANIX Public Access Internet and UNIX, NYC Message-ID: <11a91un$a7p$1@reader2.panix.com> References: <1177fdi$26ea4$1@dont-email.me> <11a5lqo$2v5bq$1@dont-email.me> <11a6870$41j$1@reader2.panix.com> <11a6a6h$37i1n$1@dont-email.me> Injection-Date: Thu, 8 Oct 2026 21:28:55 -0000 (UTC) Injection-Info: reader2.panix.com; posting-host="spitfire.i.gajendra.net:166.84.136.80"; logging-data="10489"; mail-complaints-to="abuse@panix.com" X-Newsreader: trn 4.0-test77 (Sep 1, 2010) Originator: cross@spitfire.i.gajendra.net (Dan Cross) Xref: csiph.com comp.programming:16933 comp.arch:118528 [Cross-post to comp.programming, Followup-To: comp.programming] In article <11a6a6h$37i1n$1@dont-email.me>, Terje Mathisen wrote: >Dan Cross wrote: >> In article <11a5lqo$2v5bq$1@dont-email.me>, >> Terje Mathisen 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 >>> 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.