Querying hacker news, from a browser tab (passing through a bunch of database and Web technology that make it possible for DuckDB to be executed within a browser tab)
I'd say find an angle that adds value for you (ideally both since you want the answer AND you can benefit from learning) random ideas can be:
* C++: extension to interface with GitHub workflows results (say how many times job X passed)
* JavaScript: browser-based library to visualize data
* Python: crunch geospatial data (say your own GPS data)
* ...
- Deterministic data structures (eg. a set that acts deterministic to the fact that addresses might be somehow randomly assigned, very useful for ensuring reproducibility)
Already cited, but it's clearly among the most elegant:
- union-find (!!!!)
and as a bonus one that is easily overlooked:
-std::deque, that when restricted to push_back() or push_front() guarantees not to ever move objects around.
I have to double check this, but the approach should be theoretically sound since we are quite strict with what functions are considered to have known call-sites: Function has to be internal (as in no visibility from outside) + no indirect uses (so no saving a pointer to the function somewhere). This should be enough to solve the problem you are thinking about.
I am not completely sure of what "classical" partial evaluation is, but probably yes, this is somehow a special case of it. I have now quite some material to read (see other links about partial evaluation or super-compilation).
Here by playing HumanCompiler it should be possible to prove that the if condition never evaluates to true, so removing the if is safe.
This is an example of optimization that PartialExecuter is able to do.
Note that some combinations of other optimizations might also be potentially able to get to this result (say adding a tag "is always power of 2", but doing this in a general way it's what PartialExecuter does well).
Somehow similarly, clang might be instructed to enable a check to avoid including printf_float and somehow detect it and exclude it (this is what happens here), but this is hardly generalizable.
The step forward that I believe worked well here is that given some actual paths (and since they are simply a sequence of Instruction, they can be fed to an interpreter) they are merged or forked while entering or exiting SCCs, this allows to keep a low count of actual visit but exploring a big enough set of path to prove that it covers all possible executions.
On the second part, I have to do some thinking and coming back, thanks!
PartialExecuter happens at the LLVM's IR level, and in theory it's fully generic. Then has been only partially tested outside the Cheerp-pipeline, so I would expect it to rely on some implicit assumptions on the kind of legalizations or lowering that are done before-hand.
Target-wise, all information is kept encoded in the IR, so that part is easier (the only strange thing that might happens is bumping some alignment to 8, but I expect every target to be able to handle the prescribed IR alignemtn)
I also believe it would be cool to upstream this, we will have to sit down and do some planning.
Compilation time could improve (I was actually working on this today), but it's already in line with other optimizations, taking < 10% of the time spent doing optimizations on a big codebase we use as benchmark.
Currently it's applied to all functions, since runtime it's anyhow somehow linear in the number of Instructions a Function has, but possibly in more costly versions of this (that we have on paper but yet to implement) some logic to filter functions in advance could be used.
WebAssembly implies static linking (malloc / printf & all are part of the shipped module) and code size matters since it directly influence users (since there might be delays in downloading big payloads).
Both factors plays a role in deciding to plan putting work in optimizations like this.
There are some general gains to be had with this optimization, and probably the same ideas were already around for a while, but putting together in this way was helped by thinking about WebAssembly specific constraints.
A subset of this could possibly be applied at the wasm-opt level, but consider that at the LLVM's IR level there is more information to be leveraged (in particular PartialExecuter uses information on what memory ranges are read-only).
In general the whole concept behind Cheerp (C++ to WebAssembly + JavaScript compiler) is doing as much as possible at the LLVM IR level, JavaScript concept included, since it's easier and more powerful to do code transformation there.