[HN Gopher] Beating the Compiler
___________________________________________________________________
Beating the Compiler
Author : mkeeter
Score : 78 points
Date : 2024-07-12 18:54 UTC (4 hours ago)
(HTM) web link (www.mattkeeter.com)
(TXT) w3m dump (www.mattkeeter.com)
| 0x3444ac53 wrote:
| I was overjoyed to open this and find a reference to 100r and UXN
| gumby wrote:
| IMHO the best way to think of it (well, it's how _I_ have long
| thought of it) is two lemmas:
|
| 1 - The compiler has more "fingers" than a human does. Back when
| I wrote programs in assembly I would use printout to keep track
| of what I was doing and for debugging, and so would often put a
| finger on the paper to mark where a jump was and then go to the
| destination to see if it matched up, etc. This process isn't at
| all scalable, so the compiler is inevitably going to do better
| than I ever could on anything more than something trivial.
|
| 2 - I know more about the program constraints than I could ever
| express (much less be bothered expressing) in a HLL. "All the
| values will be less than 16" or "I can use this memory location
| for something else after I've read from it" or who knows what. So
| sometimes I can chop stuff out or even rewrite the compiler
| output locally to speed it up.
|
| Also I can only do this for a few architectures...and with modern
| x86 there are so many variants with all sorts of
| microoptimization affordances that I can rarely beat the compiler
| (this is a corollary of lemma 1)
| almostgotcaught wrote:
| A compiler is a combinatorial optimizer (think bin-packing). In
| general, optimizers/solvers basically search for the best
| solution. Most production compilers don't have solvers in them,
| they use heuristics instead, but even the best solvers use tons
| of heuristics. Naturally a computer will search/try heuristics
| faster and more thoroughly than you but sometimes you can do
| better because performant searching is all about "knowing where
| to look".
| albinahlback wrote:
| While I do think there are a lot of reasons to why one should
| not write in assembly, time-critical base routines can often
| benefit a lot from being written in assembly (take GMP's mpn-
| module for instance). However, this puts some constraint on how
| the code should be formatted (in GMP's case, this means that
| everything the mpz-module does is derived from the mpn-module),
| which cannot be said for all applications.
| jll29 wrote:
| This was a good read, thanks.
|
| Instead of using unsafe Rust to optimize the interpreter loop, I
| would prefer to write a transpiler that compiles the source UXN
| binaries to local CPU binaries, which would not require making
| code unsafe/less readable and would permit further speed
| enhancements by getting rid of an interpreter loop altogether.
| mkeeter wrote:
| This is an interesting idea, but gets tricky if someone writes
| self-modifying code!
|
| There are Uxn instructions which write to RAM; _normally_ ,
| this is used for storing data, but nothing prevents programs
| from editing their own code as they're running.
| duped wrote:
| > but nothing prevents programs from editing their own code
| as they're running
|
| On some platforms writing to memory mapped in with PROT_EXEC
| will trigger a page fault and the process will be killed. In
| other words, self modifying executables are effectively
| forbidden by design (the workaround is to unmap the memory,
| map it as PROT_WRITE, modify, unmap, map it in as PROT_EXEC,
| and resume execution - which is what JITs do on MacOS, for
| example).
| duskwuff wrote:
| There's a better workaround, incidentally, which is to map
| the same memory to two different address ranges with
| different access permissions. This allows code in the JIT
| region to be updated while threads may be running in it.
| Hemospectrum wrote:
| The parent comment was referring to programs running inside
| the UXN virtual machine, which explicitly supports and
| endorses self-modifying code. Many of the creators' own
| programs take advantage of this capability, so any
| conforming implementation has to find a way to make it
| work.
| projektfu wrote:
| Good article, brings the data to back it up.
|
| Unfortunately, it was hard to read with the monokai.css theme
| because comments were nearly invisible, and a lot of your
| information was in comments. Changing the color from #75715e to
| #95917e did the trick. I guess Monokai is for programmers who
| never read comments.
| mkeeter wrote:
| Thanks for the feedback; I tweaked the brightness and pushed
| the change.
| lilyball wrote:
| Does the compiler do anything differently if you stick to Rust
| but change the dispatch implementation to be an #[inline] fn
| next() that you put at the end of each opcode?
| ajbt200128 wrote:
| > // SAFETY: do you trust me?
|
| No.
|
| Have you seen the safer-ffi crate? Then you won't have to commit
| the deadly sin of writing unsafe Rust
| Wowfunhappy wrote:
| But this is an entry point to assembly code. It's inherently
| unsafe.
| gpm wrote:
| > safer-ffi crate
|
| It looks to me like that crate is supposed to help with
| exposing rust functions to C safely, not calling foreign
| functions in foreign code safely. Am I missing something?
| 201984 wrote:
| Very cool! I enjoy seeing people writing asm, and letting us get
| the most out of our CPUs.
|
| I see you already tried what I thought of, which is getting rid
| of the jump table and making each instruction handler the same
| size. Do you think that could still work if you limited each
| instruction handler to 64 or 32 bytes instead of 256, and then
| for longer handlers jumped to a larger body of code somewhere
| else?
| JackYoustra wrote:
| Did you try PGO? This post seems like the thing it was built for.
| tempodox wrote:
| I find this strange: &mut h as *mut _ as *mut _
|
| What is going on here?
| evrimoztamur wrote:
| It dereferences a mutable reference to h twice, ignoring its
| type with _s. I suppose this implies that h is a reference type
| itself.
| muricula wrote:
| No dereferences, just casts. It shouldn't generate any
| loads/reads from memory.
| mkeeter wrote:
| It's doing the following cast: &mut
| DeviceHandle -> *mut DeviceHandle -> *mut c_void
|
| (with the pointer types being solved for automatically by the
| compiler)
| dwattttt wrote:
| It's a bit of a song and dance; you can turn a &mut T into a
| *mut T, and you can cast a *mut T into a *mut anything, but you
| can't do it in one step.
___________________________________________________________________
(page generated 2024-07-12 23:00 UTC)