Builds are all failing seemingly because of formatting issues.
As mentioned the biggest issue I have with the code is that the responsibility of optimization is with the wrapper not the operation itself. As I am not very familiar with c++ templates, I don't really know how to improve this.
However if this isn't an issue on your side, I can remove the WIP and fix the formatting issues.

Similar optimisations can be done for the modulo operator. I will file a seperate PR for that once this is merged.

Tagging @lnkuiper since I already mentioned this to him on monday

Can we create a separate divide_by_const function, and then rewrite x // C to divide_by_const(x, C) as an optimization in the ArithmeticSimplificationRule, instead of doing this optimization within the division operator?

I don't know! I don't know a lot of the internals of duckdb. I can write a function that does this, but I am not sure I can also do the optimization part of it. This does however seam like a much cleaner solution.

We avoid explicit SIMD instructions in DuckDB - and libdivide seems to contain many of them. In general it seems like a very complex library for what should be a relatively simple optimization. I wonder if we could either strip down libdivide, or switch to something like fastmod which seems to be a lot more simple.

I havn't yet tested fastmod, that was the library I was intending to use for the follow-up using modulo. One advantage of this library is that it also provides branchless versions, which may prove advantageous for automatic vectorisation. I also don't know the performance of fastmod for division
All the explicit vectorisation can be removed I think, I will look into that.

Can we create a separate divide_by_const function, and then rewrite x // C to divide_by_const(x, C) as an optimization in the ArithmeticSimplificationRule, instead of doing this optimization within the division operator?

I don't know! I don't know a lot of the internals of duckdb. I can write a function that does this, but I am not sure I can also do the optimization part of it. This does however seam like a much cleaner solution.

Have a look here, I think the rewrite should be relatively straightforward.

I implemented it as a function instead of an operator. I wasn't entirely sure where to put it, but it can easily be moved of course.

I also looked into using fastmod for division, however it only supports 32 and 64 bit integers, and doesnt support 64 bit division on MSVC at all. I also measured the performance, and it is significantly slower.

I moved this PR to use fastmod. This reduced the available types this optimization applies to, to uint32_t, but performance is around the same.

I reimplemented fastmod using the duckdb 128 bit types to allow unsigned as well as signed 32 bit execution. It is even possible to implement the unsigned 64 bit variant using this.

To get the performance somewhat good I needed the fast-path of the hugeint multiply to be in the header, as otherwise the compiler cant optimize this. I left the slow path in the c++ file, but in case of a modern gcc or clang compiler, calling the multiply function will use the optimized bath and be inlined. This makes the multiply a lot faster (if used directly, not via *).

If this looks good I can easily implement this for uint64 and (u)int{8/16}

@Mytherin @lnkuiper It's been a while, but I re-based and all the test now pass (not sure why they failed before). Are there any more changes I should make?

Thanks for the changes! I think this is actually ready to merge, @lnkuiper thoughts?

Thanks for the merge!