« first day (2321 days earlier)      last day (2853 days later) » 

00:00
@blelbach I suppose if you wanted to badly enough, you could try to do a common_type on T and *InputIterator, but nearly the whole point of passing the initial value is really to deduce the type it should use for the accumulator.
@JerryCoffin The problem is that not all of the algorithms actually use the initial value to deduce the type now.
@JerryCoffin Some of the new ones use the value type of the iterator
@JerryCoffin That init argument would not be necessary in ++11 would it?
like inclusive_scan
E.g. there's no way for me to do this correctly: gist.github.com/brycelelbach/63677e547eb957ccc879e139a0effefd
@CaptainGiraffe I don't think it ever really was truly necessary. But, for mathematical situations it's pretty common to (for example) take some floats, but accumulate them into a double.
@JerryCoffin Would your be able to off the cuff say how it would be written in c++98 without the init argument? Just curious.
00:04
@blelbach Yeah--but when accumulate was designed, I think there was unanimity (because I don't recall anything else having to solve that basic problem).
@JerryCoffin Yah
My thinking is that we adopt the following policy: if the signature takes an initial value, we use the type of the initial value. Otherwise, we use the value type of the input iterator
@CaptainGiraffe Oh, you'd have to pre-invent (so to speak) some of the iterator_traits stuff, but most of these are pretty trivial, even in C++98. Basically, you need a value_type that yields T::value_type, but has a specialization for pointers to yield *T.
@JerryCoffin Nice call, I almost want to try this now =)
@blelbach huh, doesn't it? en.cppreference.com/w/cpp/algorithm/accumulate firmly says it should deduce T = int
@sehe The standard doesn't specify that the temporary value used for accumulation must be of that type
00:10
Whatever happened to the watcom compiler? (c++98)
@blelbach Oh well. I agree the wording is unfortunately loose, but there's really little reason to expect magic since the return type, equally, it T. I'm not surprised.
I guess since std::plus<void> and friends things have been muddied a little, and the confusion should be lifted.
@JerryCoffin Ah I see
Hey I am teaching people linked lists right now
any words for them?
@VermillionAzure Yeah, linked lists sucks.
The optimizations a desktop processor is doing nowadays makes it a no brainer.
@CaptainGiraffe ...?
grammurrn
There's one thing that linked-lists are good for: writing a memory latency benchmark.
00:23
@Mysticial and pointer edumacatshion
Indeed edumacation is in play.
indead
imdead
Actually, linked-lists are in general the way to defeat processor OOE.
Ell
Ell
@VermillionAzure "use std::vector instead"
@Mysticial sorry what is OOE
@Ell indeed
00:26
out of order execution
And it will probably stay that way until processor makers find a way to do "value prediction".
@Mysticial Um, thats functional programming =)
afaik linked lists are good for one thing: writing lock-free theoretical implementations that end up slower anyway cuz in the end you're using a linked list
Most of the prediction that a modern processor is binary:
- Branch taken/not-taken.
- Load conflicts/does-not-conflict with older stores.
AFAIK, the only non-binary prediction that's done is branch target prediction. But those are very simple (always predict the same address it went last time). This is good if you're calling the same virtual on a bunch of objects that are of the same type. But not if the objects are of different types and are hitting different function pointers each time.
lock free? what?
@orlp how can linked lists be used for lockfree?
@LucDanton anything can be verbed if you try hard enough
@AldwinCheung VERB ME HARDER ALDWIN
@VermillionAzure with things like compare and atomic swap you can write data structures that do not require locking
00:33
@orlp Oh I see. So it's organized so that read/write is atomic from just the organization
??
@Mysticial would you qualify automatic prefetching as a prediction with worse cache performance as misprection cost?
@VermillionAzure "To cinch" is already a verb in this room I believe (see transcript).
@AldwinCheung cinch me harder aldwin?
I'll be glad but not in public
@VermillionAzure just read the wikipedia article, I don't feel comfortable asnwering yes/no to a single sentence summary and judge whether you understood me correctly
00:34
@orlp I thought about that, but I'll exclude prefetching because there's no cost to handling a bad prefetch. (just bad performance) Whereas for the stuff I listed earlier you need to undo execution that has already happened.
@Mysticial technically you could make coprocessors where no execution needs to be undone, you're physically splitting and abandoning the incorrect branch
I make no claims of practical feasibility though :)
@orlp Sounds about twice as useful as quantum bogo sort
@orlp I'm sure people have thought about that. But seeing as it hasn't happened yet, it might not be practical.
@Mysticial I think you could actually do something like this with a stack based machine or something like the mill
register based seems a lot harder
The most obvious case is that you use an idle core to execute other branches. But the latency of crossing cores is hundreds of cycles - which is much larger than a misprediction.
00:37
@Mysticial well you could just have duplicate pipelines for everything in a single core
not sure what that does to power/heat consumption though
And you're wasting resources (and increasing power-consumption). To the level that it's almost pointless if your branch prediction is already 90%+ accurate.
I'm not even certain if y ou can speak of a single core at that point
@Mysticial I wonder when we'll see the first neural network implemented using gates to predict branches
@orlp Well, they already have multiple pipelines for chips nowadays.
@orlp The question is whether it's predictable.
and how much power it requires and whether it's worth it
@VermillionAzure define predictable
hint: you'll get stuck in an infinite loop because your predictor exactly determines what is predictable and what isn't, nothing more
00:40
predictable has a very clear definition from a bayesian PoV
But I'd rather have one core able to utilize all the pipes for useful work than to waste half of it on running the wrong side of (predictable) branches.
So to get that right, the processor will need to include a confident factor in its branch prediction.
If its prediction is confident, keep going that route as usual. If it's not confident, then maybe execute both sides if there are available pipeline slots.
But that will hurt HT if there's another thread on the same core.
In short, I'm not so sure that sort of hardware complexity is worth it. The downsides are pretty severe (especially from a power consumption standpoint).
@blelbach without executing it
my guess is 0 because the type of the accumulator passed to std::accumulate is integer
and 0.5 gets truncated every time
to be honest I wouldn't spot it if I were glancing over the code, but considering it's an obvious trick question on twitter....
@orlp Yah
@orlp I should have been trickier
We've had explicit software prefetching for decades now. But we still don't have a similar instruction for branches. (A hint that the next branch will be taken based on the value of a register.)
The fact that it's 50/50 is disturbing :p
00:44
And the reason they don't is probably because if the user knows which way a branch will go at a point in the code, the processor is probably gonna predict it correctly anyway.
@Mysticial the more I think about it the more I become a fan of static scheduling
when I really think about it a CPU that reorders instructions seems crazy
Intel tried going back to in-order execution with the Atom. It didn't work.
You can't sell a processor if it can't run shitty code efficiently.
Because writing code that isn't shitty costs more than non-shitty code.
@Mysticial what if you made your compiler free to have better chances of people using your compiler to not have shitty code
@orlp Putting aside the fact that a compiler can't turn shitty code into not shitty code, recompiling code is apparently too high a cost.
Which is why we have the whole SSE/AVX state transition bullshit, because Intel couldn't get the industry to recompile their drivers to preserve AVX registers.
The only way this would at all be feasible if you add an extra layer of indirection and JIT everything. (which is a big selling point of managed languages)
But that still won't make shitty code not shitty.
The other thing is that static scheduling is NP-complete with fixed latencies. And it's impossible to do optimally with run-time varying latencies.
IOW, you don't know how long a memory access will take because it may or may not cache miss. And you have no idea which until you get to that point during execution.
OOE bails you out of that. If it cache misses, you keep running all the other shit in the pipeline.
Asking the user to simply, "not cache miss" is totally infeasible. I can't even figure out how to do that. And it's probably safe to say I'm a little bit better at this than the average programmer.
01:00
@Mysticial well
optimal static scheduling is NP-complete
but so is traveling salesman
yet we have very good train planners :)
and the latencies involved with 'typical' instructions are usually small (<10), and when one parameters is a small fixed integer you can usually attack np complete problems with dynamic programming
01:14
@orlp But that's not really the case with modern hardware since the "typical" instruction will be a load. And loads can range anywhere from 3 cycles to a thousand. The optimal (or near optimal) scheduling can differ drastically depending on whether it hits or misses. If you have OOE, the processor can make that decision at run-time. If you're forced to statically schedule, then which do you pick?
@Mysticial schedule loads as early as possible, if it's available at the time it's needed, great, if not, stall because we had to stall anyway
out of order doesn't change anything about that
@orlp You can't because with static scheduling, you can't move a load before a store. OOE lets the processor do that with speculation.
@Mysticial I'm confused as to why an OOE can speculate where static can not
@orlp So you saying that the speculation logic and roll-back should be implemented into the code itself?
@Mysticial no I'm saying that you can roll-back just as well in static as you can OOE
in fact it should be easier
01:20
How would you encode that?
load-that-may-alias-with-next-store-pretend-it-comes-afterward reg, address
store address, reg
Ell
Ell
@AldwinCheung You will be glad to or would be?
@Mysticial aliased stores have a very small window in which it can happen, so yes it's very easy to statically encode it like that
all a load needs is the instruction offset of the latest possible aliasing store, if that store is within the aliasing window of opportunity
and that is within ~4-5 cycles depending on your write/readback cache
@orlp So the aliasing store is the instruction right before the load.
@Mysticial first schedule your loads/stores in chronological order
then move every load up as far as you can compute the load address
@orlp Then you lose the ability to overlap the load/stores that don't alias.
01:24
say you can compute the address 20 cycles before you actually need the load
then you schedule the load 20 cycles early
and you say 'I want this in 20 cycles'
now the processor knows
store mem, reg
rand reg
load reg, mem
that only stores to that particular address can alias in 15, 16, 17, 18, 19 cycles form now
because that's the window in which an alias could occur
@orlp Reordering, as such, is just a side-effect of how the processor really works--semi-ignoring actual order, in favor of looking primarily at dependencies in resource usage.
^^ An OOE will be able to overlap the load and store provided that the probability of aliasing is low.
@orlp It changes one thing: the ability to execute other instructions that aren't related and don't depend on the result of that load.
01:28
I don't see how an in-order processor can achieve load/store overlapping on run-time addresses without resorting to the same OOE that OOE processors do. And if you do that, you're no longer statically scheduling.
@Mysticial by delayed loads that encode alias information
in such an architecture
a load must contain the following information
1. the address to load (this is your critical path)
2. in how many cycles you want the result of the load to complete (this allows the cpu to prefetch appropriately, and allows you to schedule loads 100s of cycles early preventing stalls)
3. in how many cycles the last possible aliasing store happens
with this information the CPU can statically (without needing fancy OOE logic) schedule the load, and then resolve possible aliases, and if it deems it appropriate, speculatively execute a load in spite of a possible alias
#2 How is that different from a compiler-optimization or manual prefetching? (both of which are severely limited)
#3 From a compiler stand-point that will usually be the last store before the load is supposed to execute.
@Mysticial #2 because the CPU natively supports it in a way that makes it the way to do loads
#3 correct, but the important thing is that this information is communicated to the CPU
without the CPU having to calculate that/figure that out
"Resolving possible aliases", the complexity of that logic is going to be at the same level of current memory disambiguation.
there is only a 5 cycle window
01:33
@Mysticial I can see at least one way. Make reads (and probably writes) asynchronous. That is, executing a read doesn't mean the read has completed before the next instruction executes--rather, executing it just starts the read. Then sometime later you (for example) get an interrupt to say the read has completed so you can process the result. Main thing then is to make the interrupts (or whatever) extremely cheap (e.g., have N sets of registers, each for processing one type of interrupt).
in which aliases can occur
@orlp Wouldn't that be a 100+ cycle window? (the time it takes for the longest load)
@Mysticial no, because the only thing you're fighting is the pipeline depth
@Mysticial I think it's only the difference in time between the shortest and longest (if I'm following the conversation correctly).
aliasing occurs because of pipeline depth
if you do a 100 cycle long prefetch
and during that 100 cycle window you do a store to the same address
it's trivial for the CPU to detect this, and fulfill the prefetch with the latest store
the only true aliasing occurs
is when the store is still in the pipeline when the load result is supposed to enter the pipeline
@Mysticial do you see that aliasing only has a very small window?
so if the compiler communicates those windows statically and well ahead of time through bytecode to the CPU it can statically resolve it without a bunch of logic
01:38
@orlp No I don't. Tell me how your in-order statically scheduled processor can hide a 100-cycle cache miss. Current OOE can do it if there's fewer than 160-ish instructions in that window. And there's a lot you can do with 160 instructions.
@Mysticial it can't hide all
you can write arbitrarily bad cases
well technically
but now we're going away from the practical
Oh ic. So you're not going to achieve OOE parity on cache misses.
no
but the vast majority will be similar performance
@Mysticial Not yet?
and you gain a LOT in power efficinecy
01:40
I wonder if we could... Because I bet we can
but technically you could encode all information dependencies in the bytecode
but since we seem to be limited by bandwidth nowadays that doesn't seem like a good solution :P
but maybe some innovation in the future increases bandwidth making that a viable option
@Mysticial What about VLSI architectures?
@orlp I don't doubt the power efficiency part. And I agree you can get much higher throughput using a multiple in-order cores than a large out-of-order core. I'm just saying that you're gonna have a very tough time beating an OOE processor in sequential performance.
@VermillionAzure That's a form of static scheduling.
So is SIMD.
@Mysticial I guess so eh
@Mysticial How good is the current state of the art in expressing information dependencies at the IR level?
Or, rather, where should I start if I want to read and study this?
@VermillionAzure Read up on compiler optimizations.
01:44
@Mysticial Yeah, where
@Mysticial also, how often does an OOE hide a 100 cycle cache miss where the load schedule couldn't have been moved before those 100 cycles of available work
Analyzing dependencies and stuff.
I mean, any recommended books? Dragon Book okay?
@Mysticial (yes I know you can craft such examples where it's arbitrarily bad, but real code doesn't look that way)
@orlp TBH, the project that I've been working on the last two weeks at work has been trying to figure out why our trading code sometimes can and sometimes can't hide the 500 cycle cross-NUMA cache miss.
01:46
@Mysticial would your problem be solved if you could've statically scheduled that NUMA load?
I'm the one working on this, because apparently, I'm the only person here who stands even a remote chance of figuring it out.
@orlp No because the we don't know when market data is coming in from the exchange.
oh what's NUMA?
@Mysticial how much money can you spend on hardware?
@VermillionAzure Non-uniform memory access. It's a thing on multi-socket computers.
you could speculatively pipeline many processors that assume market data is in, start processing, and start over if they assumed wrong
although I can't see that shaving off more than a couple cycles at the cost of thousands of CPUs and networking infrastructure that probably adds more delay :P
01:49
@orlp HFT is a latency-thing and not a throughput thing.
@Mysticial I know
@Mysticial fuck what is it called
the running sport
where you go in a team
and each hands a stick to the next one
relay race
yes
@Mysticial think of it like this
in a relay race the second runner always speeds up before the transfer, right?
so that they're at equal speed at the transfer
now what if you don't know when the transfer will occur?
you could just choose to stand there at 0 speed
and then acelerate when you get the stick
alternatively you could have an alternate runner start every second
That's called a spinning thread. Everyone already does that.
ah ok
01:51
bbl, need to head home.
Somehow I feel that what you guys are trying to do would be easier in Verilog/VHDL...
@Mikhail although I'm sure Mysticial isn't cheap, hardware manufactoring is very expensive
Also can you liquid cool the server :-)
plus if something changes... there's a reason it's called soft vs hardware :)
I'm thinking of an FPGA approach
01:55
@orlp Mostly what's been done is VLIW style: arrange instructions into packets, and allow the instructions in a packet to execute in parallel. IOW, you're not encoding dependencies (directly), just asserting some places that there aren't dependencies. Itanium did similar, but also allowed you to chain packets together, so you can (in theory) encode an arbitrary number of instructions to execute in parallel.
@JerryCoffin @Mysticial there's a good chance pdqsort becomes the default unstable sorting algorithm in rust btw :)
5
@jaggedSpire me in 7 hrs
@Borgleader :P I take it this is good night?
It's even worse if I dont sleep well, cuz I want to keep sleeping :P
oh yeah, definitely
02:13
@orlp Oh nice! Congrats
02:27
@VermillionAzure They probably never will. A compiler can't turn a bubble sort into a quick-sort. At the lower level, a compiler can't change your data layout to make it more cache efficient or to better vectorize. Humans can do that because they have high-level information which the compiler doesn't have.
So right now, the "best" approach is to do the high-level optimizations manually, and leave the low-level stuff to the compiler. So it's generally okay to fail at the latter as long as you can use a competent compiler. But many programmers fail at the first category as well.
That first category includes stuff like memory layout - which is something that most programmers never have to think about at all.
@JerryCoffin That will definitely help. And it's something that I've tried to do with current processors using prefetching. The problem is that it's really hard to get the timing right. Too early and it trashes the cache and gets evicted again. Too late and it doesn't help. And that timing various heavily by processor and even the work-load on the processor.
For throughput applications (like my pi program), it's hard to get any speedup at all since misses get hidden by HT. But it's easy to fuck up because bad (or improperly timed) prefetching will fuck up the cache and consume bandwidth which slows everything down.
For latency applications (like HFT), you don't need to worry about bandwidth, but cache pollution is still a huge issue. Prefetching in that environment is still really hard to do since it's a game of whack-a-mole. You kill one miss, but you don't see a speedup because there's another one next to it. So you need to eliminate all of them before you see a speedup. And I've realized that it's ridiculously hard to do unless you have a full and complete understanding of both the code and hardware.
Well, there has been reasonable progress towards optimizing the cache, and work per-element. For example, the ATLAS BLAS or Halide. One of the hard things is that on x86 the cache can't be directly accessed like on the GPU (where you can just grab a pointer to the damn thing). As to transformations like converting bubble sort into quick sort, I think I'm just not aware of them.
02:44
Haha
> Meters of the wall built
0

Number of resignations
1
> people, places and things recently insulted: Sweden, NYT, NBC, ABC, CBS, CNN, rest of media
@jaggedSpire It will be negative because it overflowed a signed integer.
@jaggedSpire Mexican immigrants?
this page is amazing
@Mikhail does it count as recent if it's just been one long insult for several months
@Mysticial lol
ICE is stepping up enforcement big time, that is the real story
02:50
> tweets: 381
@jaggedSpire I need validation bitch, star my message
9
but you didn't specify which one
jk
@jaggedSpire Works either way... unzip
@Mysticial Actually, even quite some time ago, a number of compilers did turn a bubble sort into a quick sort. At one time (early 1980s), Byte magazine did some "high level language benchmarks", one of which was a bubble sort. A few compilers "optimized" it by recognizing its text, and emitting a hand-optimized assembly language for the complete program. Unfortunately, even trivial changes to the source code resulted in serious speed loss though.
02:53
@JerryCoffin lolwut
@JerryCoffin ... which is why such optimizations are actually counterproductive: they lure the user into thinking that the code they've written is algorithmically efficient, and when it may be too late to rewrite it, the optimization bails out
@Mysticial True story. Around the same time, at least one "certified Ada compiler" used pretty much the same technique to pass the validation tests--but basically fell on its face for nearly all other code.
@Columbo This is sort of the approach to compiler vectorization atm. The compiler recognizes a pattern, then replaces it with a vectorized version. But obviously this is more general than what Jerry mentioned.
@Columbo This wasn't an attempt at productivity--it was an attempt at selling by winning benchmarks.
NVIDIA does this with their "Game Ready" driver
02:55
@Mysticial Yeah. Much more general, I presume.
@Mysticial More generally, this is peephole optimizers in a nutshell.
someone just called Trump a "cowardly jellyfish fuck" on twitter
@JerryCoffin :D
I'm impressed by the creativity. I don't encounter many insults using jellyfish as a primary component.
spineless, sure
but jellyfish just has that...extra degree of floppy
Really? Who the fuck would flag that?
@JerryCoffin If there's time left, it's probably easier to just delete since you're up to 4 now.
@Mysticial Bingo
@Mysticial Can't. I'm just contrary enough that I might not even if I could though. If they find that offensive, how about just: "Trump was given a greater responsibility than tying his own shoes"?
03:02
> The compiler doesn't have the information
@VermillionAzure It can't. For example, if you take user input and you know the user will never enter a value above 10, you can go ahead and optimize the code to not care about it. But the compiler doesn't know that and it must work correctly according to the language for all inputs as it is written.
@Mysticial Because you haven't told the compiler
This is information that the compiler does not and cannot know unless there is a way to tell it.
@Mysticial And why can't there be a way in the future?
03:05
Because the human programmer isn't going to necessarily know all the things he/she cares about.
@Mysticial There is (or at least can be). if (x > 10) abort(); process(x);
Now a sufficiently clever compiler can deduce that (in process) x <= 10, and act accordingly.
At least not until the compiler can read the feature request that the programmer acted on decide to implement it itself. But at that point, you've basically just invented the best AI in the world.
@JerryCoffin There are compiler-specific directives to do that. But I'm not sure to what extent they will take advantage of it.
But from a more practical level, the "lack of communication" issue is most apparent with aliasing analysis. And even when I explicitly tell the compiler that something doesn't alias (via restrict), they usually fail spectacularly anyway.
I don't expect compilers to change your memory layout and convert your std::vector<MyStruct> into MyStruct{ std::vector<int>; std::vector<double>}. (I'd be terrified if it did.) But aliasing is something that is close enough where I should be able to help it. Yet most compilers still don't utilize it to the extend that it can. (I'm looking at you ICC and GCC). MSVC actually does a pretty good job.
03:20
@Mysticial There are a bunch of "research" grade compilers that will do that
@Mikhail Some of ICC and GCC's -O3 optimization levels get into that category to the point where it backfires. IOW, while the transformation is legal, their cost analysis failed. And resulted in noticeable slowdown. And I often have to go through elaborate work-arounds to prevent the compiler from doing that. And then there's the fear that the next version of the compiler will be smart enough to pick apart what I did and do the pessimization anyway.
For GCC, that optimization is the memcpy() and memset() recognition. It almost always backfires spectacularly in my code. For ICC, that would be loop interchange.
MSVC doesn't do anything fancy.
Those are nice optimizations. But they need to get their cost analysis right.
Not being mature ain't the same thing as not being possible. I suspect that auto-tuning could solve some of these problems, but the auto-tuning problem might be considered NP hard...
The first issue that x86 is not transparent (to me), making everything tedious.
The one that kills me the most is memcpy() of trivially_copyable struct assignments. I usually have to define my own copy constructor that manually assigns each of the items in order to make it "not trivial" so that the compiler doesn't memcpy() it. And every time I upgrade the compiler, I fear that's going to fall apart.
What happens if you use =default?
I've tried that. No effect.
The key was to get rid of the is_trivially_copyable status.
But even that isn't enough for GCC's -ftree-loop-distribute-patterns which will recognize a lot of consecutive assignments as a memcpy(). If it ever comes to it, I will insert padding into the struct between the fields and don't explicitly copy them in a manual copy-assignment operator. (or assign junk to it)
03:33
So, memcpy only makes sense if the object exceeds some rather large size, right? So are you saying the size threshold is wrong?
Yes. And it only takes a small number of __m256i objects to exceed that threshold.
The threshold can't be a fixed number. It needs to take into account for the types inside the struct.
Hmm, why can't it just use a sizeof(T)?
...can't you get rid of trivial copying by declaring the copy constructor, and then defaulting it elsewhere? Defaulting it somewhere other than where you declare it makes it user-defined by the standard.
@Mikhail It's faster to use memcpy() a 256-byte struct of small scalar values. But it's faster to do 8 AVX2 assignments when the struct is 8 AVX types.
Just to note, the problem with memcpy() isn't so much the memcpy() itself. It's usually inlined anyway. The problem is that the memcpy() is done using a datatype of a different size from which it was written to and will read from. This causes store-forwarding stalls in the processor. The biggest problem is that it suppresses the Scalar Replacement of Aggregates optimization of the struct since the memcpy() portion of the IR destroys that information.
Yeah I figured that, it looks like they substituted memcpy too early in the optimization process. Probably, because their code is a mess of several tiers of optimization.
03:41
In many cases, when I copy a struct, what I'm really mean is "load all its members into registers". What the compiler does instead ismemcpy() it onto the stack. Then load it.
Would be interesting to see how it performs on a simpler compiler infrastructure like LLVM...
I used to not have this problem since I didn't use structs and would read the data directly from memory into local variables (which get promoted into registers). But one of the techniques that I use to target multiple ISAs with the same code relies heavily on "meta-data" structs which need to be loaded into register. And there's no other way to express that in C++ than to copy it to a local variable.
Why do you call them meta-data? Do you mean structures that mirror or mock the cache?
Probably easiest to explain by example.
In one of y-cruncher's algorithms, I need to do a vectorized 64-bit x 64-bit multiply.
And I need it to work on x86, x64, SSE2, SSE4.1, AVX2, etc...
But I don't want to write a separate algorithm for all of them.
On x64, it's just a C++ multiply.
On SSE2/AVX2, I need several intrinsics to do that.
However, those intrinsics require preprocessing of the inputs to get them into a form that they can be multiplied. So I pre-process the operands into a meta-data struct.
On x64, that metadata struct is just a single 64-bit integer. On SSE2/AVX2, it's two vector registers.
The multiply function takes two metadata structs (pre-processed operands) multiplies them and outputs the product. The metadata object provides member functions for this.
It's this metadata struct that differs (often drastically) between ISAs. But there is one code that uses them.
So when I want to extend an entire algorithm to a new ISA, all I need to do implement a metadata struct for it. And everything else falls right into place.
I'm over-simplifying a bit. As this is just one of several techniques that I use. But you get the idea.
04:01
Yeah, I got what you're saying. I wonder if the correct solution to your "load all members into registers", is wacking out some ASM and hiding it in macros, like in the linux kernel.
And because of the heavy use of metadata structs for even the most trivial of operations, there are tons of trivial wrappers - all of which need to be force-inlined. Many of these are also templated. Each vector instruction that shows up in y-cruncher's final assembly binary is probably the result of going through several layers of this shit. And that's part of why compiling the program is such a fucking resource hog.
Out of curiosity, what is your clean build time?
For a single binary within Visual Studio. It's probably like 90 seconds. For the script that builds all (now 13) binaries. It takes almost 20 min. and 30+GB of ram. For the script that builds all binaries for all 3 builds (developer, beta, release), it takes around 40 min. and about 50 GB of memory.
Core i7 5960X @ 4 GHz.
Okay you win. My microscope control and 3D image manipulation IDE takes 12 minutes for 3 GPU release "targets" (when using Incredibuild, they are compiled in).
This also means that your software takes longer to compile than FF
I realized about a year ago that I've taken this sort of programming to a level that I might as well just call code-generation.
04:20
Well, that was interesting read. Anyways I should probably go home. Its like 10:20...
I don't think I've ever open-sourced any code that uses this metadata struct technique. And I don't know if it the "idiom" is something that is new, or something that I reinvented. But it's such a powerful technique that I really can't live without it at this point.
04:51
Oh god, yeah, sounds like numerous abstraction layers just to maintain compatibility. God, finding compiler optimization bugs would be nearly an exercise in futility with that much code.
It won't be long before your code gets sentience and ports itself to Javascript :D
@Mysticial Not really new (though it sounds like you've taken to more of an extreme than most). At the ultra-trivial end, there were things like the interrupt function in most MS-DOS compilers, that had members for ax, bx, cx, etc., which (obviously enough) represented the values that would be loaded into the actual registers before the interrupt was invoked.
Most of those were pretty straightforward about things though, so they didn't try to do much automatically; for example, it just used a union of a short and a struct of two chars to represent AL/AH/AX.
@Aaron3468 Compiler-correctness bugs are surprisingly rare in such code. It sounds complicated on top, but to the compiler, it's just function inlining, basic template substitution, and implicit constructor calls. Not the kind of things that compilers tend to get wrong.
Performance bugs are easy to spot because I "know" what the assembly is supposed to look like. And if it doesn't match what I expect it to be, then I know something is wrong.
But these are all zero-cost abstractions. Initially I thought it would be a maintenance nightmare, but it turned out to be quite the opposite. Since the extra compartmentalization made the code a lot easier to test and debug.
@JerryCoffin → One of these days, I need to open-source something that uses this technique. The problem is that only things big and serious enough to warrant this sort of approach are all in my pi program or at work.
05:13
That's pretty interesting. Definitely a counter-intuitive outcome. I suppose that the modularity really helps reduce the need for clever code and helps the compiler understand contracts. Perhaps rather than open-sourcing, just make an educational blog post about a watered-down version of your metadata constructs?
After all, it's more the approach that other programmers can benefit from. They don't really need to know everything you discovered along the way.
There's primarily 3 methods that I use for multi-arch programming:
1. Vector-scalable programming: Let's me target arbitrary vector sizes. Two of my GitHub repos uses it, but not to an extreme.
2. Metadata Objects: Described here. Targets non-trivial differences between ISAs not related to vector length. Not in any of GitHub repos.
3. Include Dispatching: Let's me specialize routines for cases where Metadata Objects falls short of giving me the control that I need. This isn't new or anything. And one of my GitHub projects uses it, but not the extent that my Pi program does it.
@Aaron3468 The "clever code" tends to stay within each metadata object. And because the object itself is an abstraction, I'm free to trash it it as much as I want from a readability perspective and do all the ugly programming tricks to make it efficient. Since at the top level, I really don't give a fuck what's going on inside it.
05:38
So metadata objects carry operands that get dispatched differently depending on the arch?
It's essentially duck-typing.
Each metadata object has a clearly defined function. How it's implemented and which it is, is sort of irrelevant to the top level code.
Each metadata object lives in its own file. And there's a central header that picks the correct metadata object to include.
Going back to the 64 x 64-bit multiply. The caller knows that there exists a mul function that takes two multiplier objects (the preprocessed operands).
The multiplier object is the metadata object that can be constructed from a raw object. With this in mind, the top-level code, can create a multiplier object and reuse it as many times as it wants - thereby skipping all the redundant preprocessing for the ISAs that need it (SSE2/AVX2) - while no-op'ing for ISAs that don't need to preprocess. (x64, AVX512-DQ).
This multiplier metadata object can reside either on the stack, or in memory, or inside another metadata object.
When the metadata object is being pulled in from memory via an LUT or something, I run into the compiler memcpy() issues that started this whole conversation. If I take it by reference, then I fuck up the compiler's aliasing analysis. Hence my gripes about current compilers.
Ah, okay. I was looking at it wrong. Then you've built a virtual processor architecture that maps to all the different processors/archs. It definitely sounds like it's beyond the scope most compilers intend to support
05:54
That's one way to put it.
@Aaron3468 No its not.
damn your c/c++ adventures make me want to code c++ again ;/
@Columbo damn, that made me hope Trump resigned
06:15
@Mikhail Alright, I concede on that point.
06:53
@blelbach Wow, almost 50:50 split in the answers.

« first day (2321 days earlier)      last day (2853 days later) »