« first day (1487 days earlier)      last day (3464 days later) » 

7:01 AM
@caps In that case, the most common problem I've seen is a silly typo so names don't match.
 
Everywhere I search I see people who tried to put it in the .cpp and the solution is just "put it in the .h" but I have.
Hmm, I think I checked that but maybe not.
Thanks either way.
So.
 
If anyone needs some free flags. It looks like that branch predictor question just attracted another non-answer:
0
A: Why is processing a sorted array faster than an unsorted array?

shikjohariThis is related with the concept of Branch Prediction. As Mystical has explained it very nicely - I tried this concept with mty machine which is core i7(3.50 Ghz) with 8GB of Ram. I have tried the following piece of code and found the significant difference int arr[] = new int[32768]; Ran...

 
Thanks!
 
7:17 AM
The argument for using vector<object*> instead of vector<object> is to avoid memory fragmentation. And also you don't know how your compiler implements reallocation when it resizes, whether it is a move, copy, memcpy, etc. so the constructors / assignment operators defined for your class might not be sufficient. And if it is memcpy than you have to make sure that Object only has primitive members.
 
> found the significant difference
 
what should the state be of a moved-from vector?
 
@caps Eh, vector puts guarantees on when it moves or copies on resize/reallocate. And it sure doesn't use memcpy.
That is, if you're referring to std::vector.
 
@MarkGarcia It does? How do you know?
FWIW, I'm talking C++ 0x, if that makes a difference.
 
@caps I was once fed with the hard meat of the ISO C++ standard.
;)
 
7:22 AM
std::vector requires different things for different operations
 
Whether move or copy depends if your class has (proper) move/copy operators.
 
@AlexM. Hey, it was you who started the bdsm stuff
5
 
Starred because it's funny with no context.
 
This answer doesn't add to the discussion. Also it is exceptionally poorly written. That line you copied from the Wikipedia article is also already in the branch-prediction tag-wiki — sehe 12 secs ago
@MarkGarcia how do you plan on removing the context?
 
for example std::vector::push_back requires MoveInsertable if called with an rvalue, CopyInsertable otherwise
 
7:27 AM
@sehe Oh... Plagiarized too... wow
 
Wasn't it obvious?
 
No it wasn't.
 
The poor formatting tipped me off
 
You have a good eye.
 
guys, I'm stuck
I don't know what the state of a moved-from std::vector should be
it should be in a valid, but undefined state
apparently that means that any operation without preconditions should be succesful
 
7:28 AM
@sehe Oh damn. You! You're planning on removing the reference to @AlexM. then the message would refer to the last message... totally not giving you any ideas
 
but does for example push_back have preconditions?
I don't see them in the standard
but how can I push_back if my allocator has been stolen with propagate_on_container_move_assignment?
 
@orlp no. except, it may still fail if external conditions don't allow
@orlp That's only a precondition on the allocator. Also, if properly reserved, you don't /need/ the allocator derp. Moved-from :)
 
lol
but here's my issue
if the allocator can't succeed
I can't provide push_back
 
Indeed.
 
yet it has no precondition on the state of the allocator
so it must succeed
 
7:32 AM
I don't think indirect/transigent preconditions are documented in general.
 
Thus in these things the standard loves undefined stuff.
 
You don't see the "precondition" that "UB must not be invoked by any of the other code"
 
then, on the other hand
Allocator doesn't give preconditions for a.allocate
should I just assume the allocator must succeed to allocate, even if it's moved from?
 
Actually, I think the standard clearly spells that the operation might reallocate, and that describes exactly how the allocator will be used, which leads to your predondition!
 
(other than memory errors)
 
7:33 AM
@orlp oops. Might be an oversight then (from the "stdlib doesn't support stateful allocators" days)!
 
man this entire allocator stuff is a total mess
 
I'd tend to agree. Mostly because of the old cruft involved.
 
I'm just going to assume that a moved-from allocator is just as useful and valid as one that hasn't been moved from
since they don't specify any preconditions
@sehe another problem I see is that a = rv for some container a is marked as "linear" complexity
oh derp
nevermind
answered my own question
(destructing the old values is always at least linear)
 
@orlp On the bright side: I put together scoped_allocator_adaptor with shared memory allocation yesterday night:
0
A: C++ random access iterators for containers with elements loaded on demand

seheAs I hinted in my other answer, you could consider using memory mapped files. In the comment you asked: As far as memory mapped files is concerned, this seems not what I want to have, as how would you provide an iterator over SpecificMessages for them? Well, if your SpecificMessage is a POD...

/cc @TemplateRex
 
Xeo
Hahahaha, Clannad Kickstarter reached almost 90% of their goal in about 12 hours. /cc @StackedCrooked @AlexM. @Rapptz
 
7:42 AM
as a library user allocators are ok
but you better brace yourself for a project if you want to implement a library that accepts allocators
I'm sitting at 500 lines of boilerplate, not even implementing much real functionality in my cdeque
@sehe just getting the noexcept specifier of swap right took 2 days, 60 LOC, and a defect in the latest C++ standard
is there some constant_value_iterator<T>(std::size_t n, Args... constructor_args) that constructs and returns some type T n times?
 
@orlp When I rewrote my pi program between 2011 - 2013, some 80% of the program's 150k lines was boilerplate. No useable functionality until is was almost done.
 
@Mysticial 150kloc?
shit
let me guess, a whole lot of generalized SIMD abstraction to make it usable?
 
I consider myself patient person. But that was starting to test my patience.
@orlp In terms of LOC, the micro-optimization stuff is a lot of it. But in terms of effort required, it's small.
 
Hey @BenjaminGruenbaum Were you there for the conversation I has with puppy the other day? Anyway, if anyone can answer, he was helping me with removing calls that were unneeded in my objects (objects stopped having a draw method, they just inheritited drawable and were draw by renderer) Can anyone offer me any advice about how one might do that with audio? How would you control when the object made the noise...?
Wow crap; too long for chat :O
 
@Mysticial things like this? gist.github.com/orlp/f97ee6e0ed7064736a05
my crypto code had a lot of that =/
 
7:56 AM
The difficult part of that pi program is not the massive amount of SIMD and micro-optimization. But it's the design. Designing in a way that's flexible, performant, and amenable to micro-optimizations is very difficult. (to me at least)
Writing SIMD is just mindless grinding. Not too much effort required.
When they say that 90% of the time is spent running 10% of the code, it also applies to writing code.
 
there are some C++ wrappers for SIMD
I think they're cool
 
@Rapptz I highly doubt they lived up to @Mysticial's standards for his pi project
 
@Rapptz I have my own system for that.
 
@orlp He expressed interest in them last time.
 
But it's specialized on a per-algorithm basis.
 
8:01 AM
Compilers are very good at inlining wrappers.
 
@Rapptz They are. But that's not the difficulty.
 
like all my C wrappers have been nearly identical to the C code.
etc
 
The hard part with SIMD isn't the wrappers. But it's designing the algorithm to be optimal for all SIMD sizes.
 
compilers aren't that great at optimizing intrinsics
sometimes they work
sometimes they view the intrinsic as a black box they can't do anything with
 
8:03 AM
I spent much of my grad school days toying around with different programming methods that are SIMD-width agnostic.
@orlp When I write SIMD, the only I rely on the compiler is the register allocation.
 
@Mysticial and even about that I recall you being pissed about running out of registers
 
I don't expect them to do any of the strength-reduction bullshit.
@orlp Yes I do. But I've since become less pissed because I found a (flexible) way to program around it.
 
man I want the Mill CPU to become a thing...
everytime I look at low level stuff
 
@Mysticial I was thinking about doing a little educational project for a code generator
 
8:06 AM
does this bgm sound familiar to anyone?
 
I've found that the latest Intel and MSVC compilers have really good register allocators.
 
it's really nice
 
Even when I intentionally spill, they do a pretty damn good job.
 
@Mysticial using a simple IR where you just have infinite temporaries
 
what do the standard headers typeindex and typeinfo do?
 
8:07 AM
@Rapptz ^
 
And because of that, I can insert architecture-specific structs at the low-level and still have very good generated code.
 
nvm
Just didn't realise it was boost
 
they're in the C++ standard library too
 
@Mysticial do you think an efficient codegen IR can be abstracted beyond a register machine?
 
Not sure I understand what you mean.
 
8:09 AM
@Mysticial my idea is just infinite temporaries and register assignment at a later stage, but I don't know if that would work
 
Wait. If I'm understanding you, they already do that.
 
ah ok
 
And then at the end, the compiler solves a graph coloring problem to do the actual allocation.
 
I wonder how that'd work with the Mill
 
@orlp Nop
 
8:11 AM
@Rapptz k, thought you might like
 
@orlp Basically, every single value in a basic block is it's own virtual register.
 
@Mysticial when you say "basic block" do you mean the largest chunk of code that doesn't pass a calling convention boundary?
 
a chunk of straight-line code.
Let's not get branching involved. It makes it that much more complicated.
 
ah
@Mysticial not on the mill :P
 
When I write intrinsics, I also don't consider branches.
I'm always working on the assumption that the code will be sufficiently unrolled such that branch overhead is negligible.
 
So I never try to something like this:
29
Q: Obtaining peak bandwidth on Haswell in the L1 cache: only getting 62%

Z bosonI'm attempting to obtain full bandwidth in the L1 cache for the following function on Intel processors float triad(float *x, float *y, float *z, const int n) { float k = 3.14159f; for(int i=0; i<n; i++) { z[i] = x[i] + k*y[i]; } } This is the triad function from STREAM. I ...

The OP is trying to saturate the processor with a tight loop.
For me, I solve most problems with unrolling.
 
Oh, thanks for that @ArneMertz :)
 
I'm kinda glad I haven't reached that level of desperation yet.
 
Are you talking to me?
 
Yes
Also that OP actually answers questions.
I have a precognition that people who ask questions then 90% of the time they make all their rep from questions.
 
8:19 AM
TBH, I don't do that kind of all-out maximum CPU at all costs thing anymore.
Simply because cache optimizations are so much harder and time-consuming to do.
 
@Mysticial the cool part about the Mill is that 1. call's are atomic from the callee's view and 2. there is no global state, so there's no cleanup on either side and you only get what's returned from the call
@Mysticial so on the mill you can code branches as call and speculatively execute both outcomes of the branch in parallel, and drop the branch that turned out wrong
 
What happens if there are 10 branches? Do you speculate 1024 states?
That's one of the reasons why they don't do that in current processors.
 
I think there is a limit that you stall if you run out of speculation space
 
wow 653 kb header file
 
@Mysticial remember that there's no register file to save
@Mysticial only a very limited stack that you can even do COW optimizations with
@Mysticial but I'm re-watching the talk to see what exactly they're doing: millcomputing.com/docs/prediction
@Mysticial mispredict penalty is apparently 4 cycles
 
8:24 AM
TBH, I don't think a scalar Mill processor can beat out a massively SIMD x86 on code that is written for SIMD. But of course the Mill instructions could be SIMD itself. In which case you've come full circle. :)
 
@Mysticial ? Mill is very wide-issue with SIMD itself
you can execute up to 32 instructions per cycle as long as you have that much work to do outside of the critical path
 
I'm saying that a Mill processor executing scalar instructions, is not going to beat out a 64-wide superscalar SIMD unit on code that is able to use the SIMD.
 
but why would the mill not include such units?
 
But the Mill instructions itself could be 64-bit wide SIMD units in which case you've come full circle.
 
they cost minimal space and power consumption
 
8:27 AM
IOW, I don't think the Mill is going to drastically change the way we program.
 
oh I'm not claiming that
but it's so much cleaner on the code generation that you can improve compilers a lot
atomic calls are huge
not seeing the effects of wrong branches very cheaply is huge (this was a MAJOR issue in statically scheduled CPUs)
and then there's the entire metadata thing where you don't need overflow/floating point flags/memory access traps
 
TBH, branch mispredictions are not a big deal on the programing that we do.
Since we're not writing parsers or compilers.
 
@Mysticial basically, I think a static scheduled CPU is far superior than an out-of-order CPU, and same with a stack-based machine vs a register machine
and it is a lot better in power consumption as well
 
@orlp So they tried that with the Itanium. lol
 
@Mysticial Itanium failed because basic blocks were too small for a VLIW-type machine in general purpose code
@Mysticial the Mill deletes problems like branches that allows you to basically see any chunk as a basic block
 
8:32 AM
morning cup cakes
 
I'm looking for a lecture I saw about a year ago. It calls java class based programming and discusses "happening elsewhere code". It's about how Java isn't really OOP but is class based.
It's also something driven development or something oriented programming
 
sorry for the edit wars :(
 
@BenjaminGruenbaum sounds like some sort of 'high horse' talk to me
 
I'm trying to find it.
It wasn't a bad talk
It's a criticism on class based programming
 
@Mysticial as soon as calls are atomic from the callee you can use static scheduling through calls to external code
 
8:33 AM
@orlp I'm not familiar enough with the exact Mill design to know if they solved this problem. But suppose version 1 has 5 cycle multiplies. All the code is statically compiled to assume that. Now version 2 of the processor has 4 cycle multiplies. Does that break the already-compiled code? Version 3 will have 10 cycle multiplies, but is clocked 3x faster... Now what?
 
@Mysticial things like memory access cache misses are hidden, and don't even stall, because you can requirest memory accesses way in advance
 
@orlp You can already do that on x86.
 
@Mysticial yes, but it wouldn't be as big of an issue to leave unsolved on an out-of-order machine
@Mysticial a memory stall means the entire CPU must stall on a statically scheduled machine
@Mysticial which is why this needed to be solved in this manner
 
The problem that I described above I believe is one of the reasons why completely static ISAs have failed.
 
@Mysticial IIRC there is a translation layer at some point (I forgot if the OS must do this or the decoder does this)
 
8:36 AM
@orlp Sounds more like a JIT. :)
 
@Mysticial rescheduling these instructions is not a hard problem, and can be done JIT without any penalty
 
Instruction scheduling is NP-complete.
 
? It's a topological sort on the critical path
@Mysticial this is instruction scheduling for a stack machine
@Mysticial there are no data hazards
 
Has anyone seen "Interstellar"? Is it good?
 
@Mysticial there are no limited amount of registers up to a large point, and the compiler can do preprocessing to guarantee that the generated code will not require more than N stack spaces (this may be difficult, but this doesn't have to be done at the last moment)
 
8:41 AM
@orlp It's still NP-complete.
That said, it's probably possible to get close to optimal with some good heuristics. But instruction scheduling is by no means an easy task.
Current compilers use polynomial-time heuristics.
 
I fail to see what makes it hard
are you assuming things like limited execution units?
 
Just google for "instruction scheduling np-complete" and you'll get plenty of papers to read.
I studied this myself in grad school.
 
@BenjaminGruenbaum you mean like the way Java people freak out at the idea of a ... free function?
 
It had a name
 
data driven programming
 
8:44 AM
There are some restrictions that make it no longer NP-complete. (I think fixed-latency might be one, not sure though.)
 
I wish you could do pull requests for gists
such a pain that you can't
I know they're not 'repositories' but for single files it's better than making a local git repo
you can already clone and fork :<
 
@Mysticial I don't think it's NP complete
@Mysticial or at least, you can make the JIT part not NP-complete
@Mysticial you don't have to deal with branches, you don't have to deal with data hazards, you have fixed latencies, you get arbitrary preprocessing time in the compiler
and the processor is very wide issue (32 instr)
 
@orlp By "fixed latency", I mean, all instructions have the same latency.
Not that they all execute in a fixed # of cycles.
 
ah
 
Latency isn't the only constraint. The other dimension is execution units and which ones are shared. That makes it even worse.
Optimally scheduling through that, is much harder.
 
8:50 AM
you just have one critical path per execution unit?
as long as your ILP < your issue width I don't see the problem
and unless your code has ILP > 32...
 
When certain instructions can only go into a subset of execution units. And some instructions need multiple execution units, it is the optimal packing problem. Which itself is NP-complete. That said, I can't imagine a processor having so many execution units and complicated instructions that it would actually be difficult to solve.
 
I hadn't considered one instruction needing multiple execution units
I don't know how it works then
 
Oh yeah, many x86 instructions go to multiple execution units.
 
I wonder if the same is true for the Mill
 
As in, they require going to multiple execution units. And there is some flexibility to where they can go.
 
8:53 AM
the thing is, 80% of the power in x86 is spent in being a register machine: all the renaming bullshit, piping data from A to B, etc
 
It makes it NP-complete to solve optimally.
 
The struggle is real (me this week).
 
@orlp Part of the problem is that x86 packs a lot into each instruction. If you split it all up, then it's easier to solve. But now you have a lot more instructions to schedule.
 
@Mysticial here's the thing, I don't think it's NP-complete if you're not realistically limited by issue width
@Mysticial yes!
@Mysticial but the mill solves that and has a issue and scheduling width of 32
@Mysticial non-out-of-order scheduling is a lot cheaper
 
@orlp I'm not arguing that.
I'm only saying that instruction scheduling, in all but the most trivial forms, is NP-complete.
 
8:57 AM
@BenjaminGruenbaum most things do
 
@Mysticial I think the constraints the Mill provides allows dynamic JIT portable executables between models with different latencies
@Mysticial I'm going to rewatch the entire series again to refresh my memory and I'll tell you what their solution is if I figure it out, or whether they leave it unspecified
 
so what? x86 is also portably JITtable between different models.
 
@Puppy the Mill is statically scheduled, not out-of-order
 

« first day (1487 days earlier)      last day (3464 days later) »