VM code refactor - thoughts?

Request For Comments
#1

Hello! As I mentioned in What is the status of SWI-Prolog ported to WebAssembly, I’m working on enhancing swipl’s WebAssembly port. It’s going along fairly well, with the one unfortunate exception that pl-wam.c takes approximately 180 seconds to compile, and it won’t even run (PL_next_solution() gives a runtime error: "Too many local variables") when compiled at -O0.

So I’ve started down a separate path of refactoring the WAM code away from the one-big-function paradigm and towards one-function-per-instruction. My thought is to kill two birds with one stone - to allow compilation on WASM regardless of optimization level, but also to make the control/data flow more explicit, to give modern compilers more of a chance to optimize.

Initial results are promising - I have a prototype function-mode build (currently compiling to native Linux/64/gcc), and there’s no noticeable performance difference between that and either the switch-mode or goto-mode builds: the ctest suite passes all tests, and it takes close enough to exactly the same amount of time in each mode that I’d probably need to average out over a couple-hundred runs just to tell which was fastest. Is there a better benchmarking test that I can run?

Core devs, especially @jan - what are your thoughts on this move? Should it be restricted to the WASM build? If it proves to be as performant as the single-function version, should the old version be removed entirely given the clutter it requires in PL_next_solution()? Should it go even further? I can already think of some potential mechanisms that this model would enable, including the possibility to precompile sequences of WAM bytecodes to C, perhaps even whole procedures, with full optimization.

2 Likes
#2

First the simple questions …

Run (from the toplevel of the souces):

swipl bench/run.pl

As for performance, the real test is to build the PGO optimized version as anyone interested in performance is using that. Depending on the platform it can be up to almost twice as fast as the normal -O3 build.

I did this at least 20 years ago. The fact that in the current VM the instructions look “function like” while they are in fact code fragments in a giant procedure are the remains of that :slight_smile: It surely made the code a lot cleaner, but also about twice as slow and thus I reorganised the code to be effectively a single function but looking as close as possible as a set of functions.

Hardware changed (I was probably using SUN on SPARC those days) and notably C compiler technology improved a lot.

So yes, if it proves to have the same performance using the current technology I’m all in favor! I assume this means we have an array of function pointers, no? If so, we can also gain some performance by specializing VM instructions that use dynamic tests for debugging, signals and some more (currently mostly packed under the alerted flag) and swap the function pointer. Also creating mega instructions (replacing a common sequence of VM instructions by a single one) is a lot simpler. That used to be an important optimization technique. I’m unsure how useful it is these days.

Looking forward!

#4

@dmchurch do you know whether this multithreading support could also get us a working Prolog console in browser? Currently the blocking read call deadlocks the event loop leaving no way for the user to provide data for the read call.

#6

It absolutely can! I haven’t actually gone and made a page-based console or anything, but I’ve used low-level primitives with my test build and it runs just fine. (In fact, it doesn’t even need to use a multithreaded build - having the Prolog code running in a worker solves that issue on its own.) That’s not the direction I’ve been directly pointed in, though; my MVP has been “get pengines working, run Swish against in-browser implementation”. And that’s currently sitting behind “convince WebAssembly to shorten my compile-test time below three minutes”, ha.

1 Like
#7

Aha! Fantastic fantastic info here, @jan, thank you so much. Once I’ve gotten my function-mode code in slightly neater order I’ll publish the branch to my fork, even if I’m not quite ready to send in the PR yet. I’m looking forward to seeing what kind of proper benchmark results I can get!

And yes, I’m currently trying two implementations, using the same VMCODE_IS_ADDRESS switch, one with an array of function pointers mapped to codes, the other as raw function pointers emitted by the compiler. There’s much less advantage to be gained from the latter, though, because you can’t force a C compiler to tailcall, so it’s gotta return to PL_next_solution() prior to dispatching the next function no matter what.

It also occurs to me that swapping out function pointers would be a good way to support something like processor-specific optimizations determined at runtime, so that’s cool too.

Anyway, I’ll keep you in the loop as to how it goes!

#8

I haven’t kept up with C compiler technology, but: c - Is it possible to force tail call optimization on GCC/Clang? - Stack Overflow

BTW, if you’re having trouble with getting gcc or clang to optimize the way you want, I have some connections to people who work on the compiler, and might be able to get some advice from the gurus. (No promises – I haven’t talked with them for over 3 years and I know that they’re very busy.)

#9

Ha, I think I saw that very SO post! Unfortunately, as I discovered when I made a little test cradle, while I can easily enough convince a compiler to do tail recursion without growing the stack, I can’t get it to tailcall a sibling function the same way (even if they have not just the same arg types but also the same arguments). If you’d like to dig into it further, by all means go ahead, I’m certainly curious! Don’t go to too much trouble, though - while saving on the function prologue/epilogue execution time would certainly be nice, my biggest reason for wanting to go the tailcall route would be to help the compiler understand the control flow better, and if there isn’t any general support for TCO, I doubt there would be that much optimization effort put into a -fforce-experimental-tailcalls option or something of the sort.

#10

As for @peter.ludemann, what we are dealing with here is to map a VM instruction to a function one-to-one. This means running the VM is typically something like:

for(;;)
{  (*vmi[*PC++])();
}

Now I think @dmchurch wants to save the function pointer in the VM code (as the current version stores the switch addresses in the VM code using GCC’s &label syntax to get the address from a label). Now we can get this code (disregarding arguments):

for(;;)
{ (*PC++)();
}

Ideally however we would not have to do this, but instead have the VM instruction doing what is below. This would work fine if the C compiler would do last call optimization (also in debug mode b.t.w. as otherwise debug mode would become useless).

some_instruction()
{ <do some work>;

  (*PC++)();
}

I’m not sure I would like this anyway as one of the nice things about having the VMI instructions returning is precisely that they return :slight_smile: That would allow getting rid of various dirty hacks and allow for easy to maintain “jumbo instructions”. It is not unlikely that gains more than it looses.

I’m probably in any case in favor of using a function pointer array as that allows is to dynamically adjust the VM instructions between debugging and normal execution versions.

P.s. another interesting benchmark set is here: my-prolog-lib/peirera.pl at 188108f67b0c9edc1a0274a4bf0e39d54cd62cdc · JanWielemaker/my-prolog-lib · GitHub

1 Like
#14

There’s really no security implications here. If you have access to write arbitrary values to arbitrary locations (which you would need to alter the opcode table - which already exists in swipl, by the way), you already have full control of the system. The simplest and most common tactic at that point is just to overwrite the return address of the current stack frame, in which case the host processor itself will jump to any address you like. And even if not that, the swipl VM has the FCALL functionality and opcodes, which instructs it to call whatever function pointer you pass it.

Much like with hardware microprocessors, the security implications need to be addressed at a higher level than the VM implementation - in this case, via sandbox functionality.

1 Like
#16

I recall looking at some embedded software requirements (MISRA?), and they didn’t allow recursion (because of the possibility that the stack could overflow). And there were a lot of other standard software practices that were not allowed. So, I somehow doubt that Prolog would be accepted, at least at the lower levels, even though it could greatly simplify that software. (If you want to see truly scary stuff: Better Embedded System SW: A Case Study of Toyota Unintended Acceleration and Software Safety)

At a higher level, there are probably already interpreters for things like javascript (or Java, for that matter, if Android Auto is used; although maybe Dalvik nowadays compiles to machine code), so whatever security issues are used at that level, something similar could probably be done with Prolog.

#17

For anyone who’s interested, my initial barebone tests are showing about a 20% performance loss on the VM-as-functions version (testing a PGO gcc9 build for both), which isn’t a bad place to be starting from! I’ll be pushing the code to my repo at some point later tonight.

1 Like
#18

Is this on a recent x86? I wonder what the performance difference would be on M1? The x86 needs to spend a lot of transistors to make up for the design flaws of the x86 ISA; the M1 can spend the transistors on things like fancier branch prediction and better caching …

(Some years ago, I did some performance investigation of Quintus Prolog on PowerPC … it turned out that some undocumented architectural features of the PowerPC made it run much faster than IBM’s “Red Book” calculations)

#19

Yes, this is on my laptop, which has an 8th-gen i7. And, considering this really is just a 1:1 translation - the processor is doing all the same steps it was doing before in the branch model, only now with added stack transitions - I’m not particularly surprised to see it take a hit! It’ll be interesting to start doing some profiling and see where the time is getting eaten up.

#21

I only know it has been audited in financial and telecom contexts. Both resulted in a couple of things to improve where it was unclear there was a bug or not but there was a simple way to make the code obviously right. The VM itself is far too hard for automated tools to proof its safety. I guess that holds for most VM based systems.

#22

Is this difference a lot more than the non-PGO version? You claimed nearly no difference before. That made me excited as a function based approach can also simplify and speedup some things so we would end up with something both faster and cleaner. Recovering 20% could be a challenge and there are too many users who will be pretty unhappy to hear about any significant performance loss. We’ll see …

#23

With an approach similar to the one below you should not get any performance penalty and full inline.
This will permit also to have a debug and non-debug run.

#define VMIS vmi(0) vmi(1) vmi(2) vmi(3) vmi(4) vmi(5) vmi(6) vmi(7) vmi(8) vmi(9) vmi(10) vmi(11) vmi(12) vmi(13) vmi(14) vmi(15) vmi(16) vmi(17) vmi(18) vmi(19) vmi(20) vmi(21) vmi(22) vmi(23) vmi(24) vmi(25) vmi(26) vmi(27) vmi(28) vmi(29) vmi(30) vmi(31) vmi(32) vmi(33) vmi(34) vmi(35) vmi(36) vmi(37) vmi(38) vmi(39) vmi(40) vmi(41) vmi(42) vmi(43) vmi(44) vmi(45) vmi(46) vmi(47) vmi(48) vmi(49) vmi(50) vmi(51) vmi(52) vmi(53) vmi(54) vmi(55) vmi(56) vmi(57) vmi(58) vmi(59) vmi(60) vmi(61) vmi(62) vmi(63) vmi(64) vmi(65) vmi(66) vmi(67) vmi(68) vmi(69) vmi(70) vmi(71) vmi(72) vmi(73) vmi(74) vmi(75) vmi(76) vmi(77) vmi(78) vmi(79) vmi(80) vmi(81) vmi(82) vmi(83) vmi(84) vmi(85) vmi(86) vmi(87) vmi(88) vmi(89) vmi(90) vmi(91) vmi(92) vmi(93) vmi(94) vmi(95) vmi(96) vmi(97) vmi(98) vmi(99) vmi(100) vmi(101) vmi(102) vmi(103) vmi(104) vmi(105) vmi(106) vmi(107) vmi(108) vmi(109) vmi(110) vmi(111) vmi(112) vmi(113) vmi(114) vmi(115) vmi(116) vmi(117) vmi(118) vmi(119) vmi(120) vmi(121) vmi(122) vmi(123) vmi(124) vmi(125) vmi(126) vmi(127) vmi(128) vmi(129) vmi(130) vmi(131) vmi(132) vmi(133) vmi(134) vmi(135) vmi(136) vmi(137) vmi(138) vmi(139) vmi(140) vmi(141) vmi(142) vmi(143) vmi(144) vmi(145) vmi(146) vmi(147) vmi(148) vmi(149) vmi(150) vmi(151) vmi(152) vmi(153) vmi(154) vmi(155) vmi(156) vmi(157) vmi(158) vmi(159) vmi(160) vmi(161) vmi(162) vmi(163) vmi(164) vmi(165) vmi(166) vmi(167) vmi(168) vmi(169) vmi(170) vmi(171) vmi(172) vmi(173) vmi(174) vmi(175) vmi(176) vmi(177) vmi(178) vmi(179) vmi(180) vmi(181) vmi(182) vmi(183) vmi(184) vmi(185) vmi(186) vmi(187) vmi(188) vmi(189) vmi(190) vmi(191) vmi(192) vmi(193) vmi(194) vmi(195) vmi(196) vmi(197) vmi(198) vmi(199)

int x;

#define vmi(n) void vmi_##n(void) { x = n; }
VMIS
#undef vmi


void run(int *x) {
  while (*x) {
    switch (*x) {
#define vmi(n) case n: vmi_##n(); break;
      VMIS
#undef vmi
    }
    ++x;
  }
}
#24

Thanks. If I understand this correctly this allows for both a function based and switch based approach using the same source, no? Defining the code in a macro makes the code pretty unreadable as we need \ at the end of each line and to the debugger the whole thing becomes one line :frowning:

I don’t know what @dmchurch did. a VMI now looks like this (as I think you know):

VMI(H_FIRSTVAR, 0, 1, (CA1_FVAR))
{ if ( umode == uwrite )
  { setVar(*ARGP);
    varFrame(FR, *PC++) = makeRefG(ARGP);
  } else
  { varFrame(FR, *PC++) = (needsRef(*ARGP) ? makeRefG(ARGP) : *ARGP);
  }
  ARGP++;
  NEXT_INSTRUCTION;
}

This tells the system there is a VMI named H_FIRSTVAR with no special properties (0 is a flag field) and one argument which is the offset of a first var, i.e… an environment variable seen for the first time. By defining VMI appropriately it is pretty easy to turn this into a function. NEXT_INSTRUCTION means go on and there are a couple of other macros that tell tell system to backtrack or continue execution in another VM instruction. These can simply be translated to return some_code.

This should be pretty straightforward. A serious problem is that some VMIs share some variables and (typically) several VMIs prepare some of these variables before jumping to a common implementation. That requires a bit more restructuring. I’m curious how @dmchurch handled this. Who knows. Maybe we have some clever people around that find a way to make the system cleaner and faster :slight_smile:

#25

The variables passing should be handled with argument passing to common helper functions.
If we want to preserve both the function and switch based approach, we should introduce some macros for such gotos.

#44

Incidentally, they are all mammals.

#60

I agree that comparison on the same machine with the two implementation models is useful; but I also caution that laptops often have poorer performance for the same CPU than desktops (and mobile-optimized CPUs are often significantly worse than similar desktop-optimized CPUs, and that’s without getting into details of the other chips); and a VM is the kind of thing that can be greatly affected by things like caching, memory performance, hyperthreading.

In a past life, I had to tune a finite-state machine … IIRC, I got something like 5x by examining instruction-level traces and doing things like reordering if-then-else’s and judicious inlining. (I wonder how PGO plays with [[likely]] and [[unlikely]] – and are these the same as __builtin_expect?) I also tried 4 different compilers and got very different results. Compiler choice and specific optimizations mattered a lot on a RISC machine, not as much on a CISC (x86), hence my musings about M1.