moonchild

Later version allowed to scan from arbitrary position by mirroring first bucket as last

you may find my improved table design of interest, which avoids the need for mirroring: https://outerproduct.net/trivial/2022-10-06_hash.html

suppose the data were generated by a csprng with 256 bits of state. then in fact there are just slightly more than 256 bits of entropy there (prng state plus the length of the generated file). only, you'd have a snail's chance in hell of actually finding that seed

"the" instance

i suppose you can probably do anything with dependent types, but i'm not sure this is a useful perspective. i commend you to read my comments on the red website https://lobste.rs/s/xkcrvn/

(i do think it is a valid question whether abstract interpretation is a good idea)

they are talking about treating ocr as lossy. i wonder about making a lossless compression algorithm for text scans based on an ocr; in effect, use the ocr to predict which text will show up and how, and then encode the pixel-level differences on top of that

they should be integers

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

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

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?

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

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)

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

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

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

float

hm ...

  >>> def percent(progress, total):
  ...     return round(99 * progress / total + 0.5)
  ...
  >>> x = 9007199254740990.0
  >>> x - 1 < x
  True
  >>> percent(x - 1, x)
  100

alignment granule

if you have metadata to identify object starts then you can do 1 bit per min object size (which can be bigger than the alignment granule)

even single-output is a dag; you can explode the dag into a tree, but then you pay in time. suppose some expensive term x is used to compute n other terms. after computing x, assuming we want to share it, we have to compute all n terms before killing x; hence x sticks around longer than it might. (this doesn't necessarily lead to explosion, but i'm pretty sure you can use this to construct a scenario that needs a large number of live terms to avoid compromising time complexity; at least n live terms if the dag has nlogn nodes)

greenspun's tenth rule:

Any sufficiently complicated C or Fortran program contains an ad hoc, informally-specified, bug-ridden, slow implementation of half of Common Lisp.

i would do a variable-size header 4 or 8 bytes for most small objects (8 if you want to provide alignment, 4 if not or if you can squish your pointers). one bit identifies if the header is small or large; if small, next few bits give the size of the object in words, and the remainder are a bitmap telling which words are pointers. forwarding pointer stomps on the first word of the object

(dynamic) computation forms a dag, not a tree. i think a sum scan (n inputs -> n outputs) will trigger the worst case. it might be that computations tend to be tree-shaped, so you rarely hit the worst case, but that helps everybody out, not just affine arithmetic

feel free to ping on irc if interested in chatting more on the topic, though i'm not sure i have a ton more original thoughts atm

if you have an expression with n terms, then you will end up with O(n) terms each taking up O(n) space, so the overall space usage is quadratic. (that's the fair way to compare to polyhedra since they're always global)

so a middle ground (as many pseudo-symbolic approaches). glanced at wikipedia—this seems not dissimilar conceptually to the abstract domain of polyhedra, in that it's symbolic but has a flat structure and expresses only linear relationships. of course, polyhedra are exponential where affine arithmetic is quadratic (overall space in number of terms), and polyhedra are global where affine is local (therefore easier to implement as a library, but no sharing). more missed connections between numerical analysis and program analysis? (meh but no sharing probably means affine generally loses for a given resource budget. would still be interesting to try though)

you may find this interesting if you haven't seen it already: https://fredrikj.net/blog/2017/11/new-rigorous-numerical-int...

this requires all terms to be represented symbolically, which 'works', but now you need a full-blown symbolic rewrite engine to try to simplify things. very reasonable for an optimiser but not so much for numerics. for numerics a more common approach is interval mincing. we have a function f(x) = x*x, and try to apply f([-3 3]). we can 'mince' the inner interval and say that (e.g.) [-3 3] = [-3 -1] U [-1 1] U [1 3]. so we have f([-3 -1] U [-1 1] U [1 3]); distribute function application over U (which is sound) to get f([-3 -1]) U f([-1 1]) U f([1 3]), which is obviously tighter than f([-3 3]). we picked a subinterval size of 2, but can shrink it arbitrarily until we're satisfied with the result. this technique is essentially a form of case analysis, and can also be applied to optimisers/static analysers (complementarily to simplifying rewrites)

see xsum https://gitlab.com/radfordneal/xsum

yup, jitter does that too; e.g. https://ageinghacker.net/talks/jitter-slides--saiu--bts-2022... page 23 and 35

fwiw i thought this was a stupid, hacky, pointless approach when it was called jitter and i still think it's a stupid, hacky, pointless approach when it's called copy-and-patch ;)

but still like to see credit where it's due

piggy back on the existing C compiler and whatever backends it already supports

that is the whole point of jitter

Isn't copy and patch just jitter: new fangled kids' version?

I still don't see what you're getting at. What is the implication of this for software? The implementation of the cache coherency protocol is largely opaque to software.

Tbf you could say stores happen in order, and loads can happen out of order unless you fence. Personally I don't understand why we need such strong ordering constraints for weakly ordered reads—istm you can go much weaker and maintain sanity.

see the phrasebook https://www.jsoftware.com/help/phrases/contents.htm

CPU's with data caches can to smart things with architecturally-defined locking instructions such as "test-and-set' or 'compare-and-exchange' such that the instructions are always cache-coherent across CPU's. If you try to roll-your-own locking code, you had best understand how the cache invalidation mechanism works in your chosen CPU or you are going to have a bad day.

What do you mean? Are you implying that read-modify-writes are treated differently from plain writes by the cache coherency protocol?