moonchild

i am not cheating; you are cheating by trying to do integer arithmetic instead of float arithmetic. in particular: 99 * progress is a (potentially big) integer; then the quotient, from my understanding of python, is equal to the mathematical quantity rn(99 * progress / total), which is not trivial to compute. (although cpython does tend to do a particularly bad job of this sort of thing.) (compare with c or with my version of the python, where it would be rn(rn(99 * progress) / rn(total)), rounding twice, which is very easy to compute. i'm not saying the c semantics is better, mind.) when you scale up by 10x, the numerator is <1/2 'ulp' away from the denominator, and so the quotient rounds up to 99 exactly; there is still double rounding (would have been triple rounding in c and my python), because we got rn(rn(99 * progress / total) + 0.5) where what we wanted was rn(99 * progress / total + 0.5) (which is mathematically always the correct result)

i agree it is not common to have so many steps. but if i were providing a routine that was intended to be robust where others were not, i would try to be comprehensive. and i would not try to do int math with floats unless i could show it to be robust (i have sketched such a stunt! https://gist.github.com/moon-chilled/60bd2ba687dc197d93a9d22...). the integer routine is simpler and more honest anyway, and it is obvious that it works uniformly for the entire range

note also that, with x floating, the python expressions 10 * x and 10 * x - 1 are equivalent, meaning the error is on input to the percent function. (if we set progress to 10 * x - 8, the immediately preceding fp number, we do get 99, but there is no deep reason for this, and it differs for different values of 10.)

> if your username is named after the band, good taste :)

my username comes from a book: the neverending story. i am more using the german version of the name these days but i do not feel like making a new account on this godforesaken website

Comment · 2 years ago

depends how you define causality. if you consider the execution of one operation to cause the execution of the next operation in program order, then causality was already broken by simple reordering. if it's a read-write dependency, on the other hand, then it won't be broken (because cpus respect control dependencies); hence, you cannot, for example, replicate oota this way. what's broken is specifically read-read data dependencies. and only on weakly-ordered architectures; it won't do anything on x86

Comment · 2 years ago

> I've never heard anything about these sorts of graph algorithms being possible with good asymptotics in an array style

yeah—idk graph algos really, but have heard parallelising combinatorial search in general (eg sat) is hard because forks and joins happen heterogeneously and erratically. this 2001 vintage has a bunch of completely sequential graph colouring algorithms in j https://dl.acm.org/doi/pdf/10.1145/570406.570416 (and j at least has sparse matrices!)

> Constant lifting within the compiler is pretty cool, I'll have to look into that.

hrm, it seems to refer to 2 things: 1) constants allocated in a special space; 2) interning. 2 is obviously worthwhile; 1 i would guess is related to memory being weird on the gpu?

Comment · 2 years ago

what exactly do you mean by 'global parse'? it's very usual, i think, when operating on data stored in files, to parse them into in-memory structures before operating on them? but it feels like you are talking about something specific to vector rendering

slug builds acceleration structures ahead of time. the structures are overfit to the algorithm in a way that ttf should be but which is economical for video games. that doesn't seem like an interesting concern and nothing about it is specific to the gpu

Comment · 2 years ago

lengyel told me he has implemented some sort of hinting on the gpu for slug (i suspect it's not programmable, but didn't ask)

Comment · 2 years ago

programmable hinting was already a thing. it's just switching to wasm from a bespoke language

Comment · 2 years ago

> 1/t^p

i don't think that's right. it's just 1/t. after all, after t time, one task must have made progress; since there are t tasks, the probability that i'm the task that made progress is just 1/t

the primary point of confusion, i think, is that getting interrupted does not mean that you are necessarily going to lose the cas

Comment · 2 years ago

i saw this last week and was incredibly confused. aside from being naive it's totally overfit where general approaches are very well known??