5 ms·
Easy to remember, but may take some time to grasp: Arrays.sort( {lower_bound, num, upper_bound} )[1]; Next challenge: teach the optimizer to make that almos
by Someone 6y ago
Easy to remember, but may take some time to grasp:
Arrays.sort( {lower_bound, num, upper_bound} )[1];
Next challenge: teach the optimizer to make that almost as fast as the min/max way ;-)
(You can’t reduce it to the min/max call because it also works if you accidentally pass a lower bound that’s larger than the upper bound. Worst-case, the above takes 3 comparisons, unless at least two of the inputs are constants)
- chrisseaton 6y ago> Next challenge: teach the optimizer to make that almost as fast as the min/max way ;-) I did exactly this for my PhD! https://chrisseaton.com/phd/ https://chrisseaton.com/phd/
- TimTheTinker 6y agoFor those reading, this work went into TruffleRuby, which implements Ruby on top of Truffle/GraalVM.
- ford_o 6y agoWait, how is that not trivial?
- saagarjha 6y agoIt's not just a hardcoded optimization for that construct.
- chrisseaton 6y ago> how is that not trivial? It could be trivial to implement an optimisation which does this for that exact code. But what are you going to do? Hand-code an optimisation for every similar thing people could write? I implemented a general solution. So it also works through metaprogramming: [1, 2, 3].send(:sort).send(:[], 1) Through user-defined sorting order: [1, 2, 3].sort_by { |a, b| b <=> a }[1] When nested: [[1, 2].sort[1], 3].sort[0] And so on. Note that it also needs to be transparent to debuggers and profilers, it needs to handle multiple method redefinitions (for example what happens if someone redefines the sorting order for integers). It's not a pattern-matching optimization - it's partial evaluation enabled by a new kind of polymorphic inline cache.
- azinman2 6y ago> But what are you going to do? Hand-code an optimisation for every similar thing people could write? While I appreciate that you solved the general problem, I wonder if there are legs here. Specifically, could one mine GitHub to find automatically common patterns that one could write specific optimizers for, or at minimum, leverage that to learn what semi-general cases are worth optimizing? To my knowledge optimizing compilers already do have effectively handlers for common operations, but I don’t know if anyone has leveraged “big data” to help guide this. IIRC, various tweaks and optimizations in Java were guided by Sun analyzing their own code based. GitHub is just so much bigger, and polyglot.
- Lerc 6y agoI'm glad things like this are being worked on. I have been writing a set of implementations of the nBody benchmark in JavaScript using various forms of abstractions. In an ideal world they should all take the same speed since they perform the same fundamental task and produce the same result. They just represent different scales of optimization effort. It's interesting seeing the difference between vectors in arrays vs objects and if you do immutable versions. The trickiest to optimize form is using a micro vector library which uses closures and array map(). var vop = op => ((a, b) => (a.map((v, i) => op(v, b[i])))); var vdiff = vop((a, b) => a - b); var vequals = (a, b) => { return (vdiff(a, b).reduce((c, d) => c + Math.abs(d), 0)) === 0;}; var vadd = vop((a, b) => a + b); var vdot = (a, b) => a.reduce((ac, av, i) => ac += av * b[i], 0); var vlength = a => Math.sqrt(vdot(a, a)); var vscale = (a, b) => a.map(v => v * b); var vdistance = (a, b) => vlength(vdiff(a, b)); Currently on my lowly atom laptop and FireFox. The version using mutable objects is ten times faster than the mapping immutable array version. I live in hope that one day there will be an optimizer that turns var transpose = matrix => (matrix.reduce(($, row) => row.map((_, i) => [...($[i] || []), row[i]]), [])); var multiply = (a, b, ...rest) => (!b) ? a : multiply(a.map((p => transpose(b).map(q => vdot(p, q)))), ...rest); Into a CPU optimum (or dare I suggest GPU) version of a matrix multiply.
- deleted 6y ago[deleted]
- Aperocky 6y agoVery noble, but I'm assuming (hoping) the technique will be more generally applicable than Ruby?
- xxs 6y agothis doesn't work for NaN, e.g {0d, Double.NaN, 1d} returns 1d.
- jrochkind1 6y agoDoes NaN have an "order" in the set of reals or integers or whatever? I would have no idea what to expect from `min(NaN, x)` or max same. But is it specified by an IEEE standard or something?
- loeg 6y agoNo, the only valid result for NaN is NaN. Saturating range bounds are for real numbers.
- xxs 6y agoBoth min and max should return NaN, if any of their parameters is NaN. Sorting can be defined where to place the NaNs (head/tail) but it's largely irrelevant in this case as simply the substitution won't be permitted by any compiler. NaN is part of IEEE754 but of course it's not a 'real' number (integer numbers don't have NaNs) Edit: you can consider NaN (and to a degree both infinities) as an exception, once it occurs - it has to be propagated. Any operation involving NaN should be returning NaN, any operation comparing NaN to anything has to return 'false'. That includes "if (NaN == NaN)". boolean isNaN(double d) is effectively "return d != d;"
- noctune 6y ago> Both min and max should return NaN, if any of their parameters is NaN. That's not a given, though. IEEE 754-2008 defined min and max as returning the non-NaN parameter. They have been removed in IEEE 754-2019 though.
- xxs 6y agoThe reference to IEEE 754 is made later on, mostly to answer the question posted. I meant regular functions in C alike languages - Math.min/max - java/javascript, fmin/fmax - C++. They do the "right" thing to propagate the NaN
- mabbo 6y agoYou know what's great about that? The order of the arguments doesn't matter. So all the debate about "should it be num, min, max or min, num, max"- your solution does not care. Put them in any order you like! You've redefined the problem from clamping a given value into picking the middle value from 3. This is a lovely way to re-interpret it.
- thaumasiotes 6y agoWell, the order of the arguments does matter. Sorting three values requires 2.67 comparisons where clamping a value between two other values requires exactly 2. There are plenty of contexts where cleverly avoiding a problem by doing 33% more work isn't viewed as desirable.
- jonahx 6y agoTrue, but I think there are more situations where minimizing the chance of programmer error, now or in the future, is more important than a micro-optimization that will never matter. All depends on context.
- fizixer 6y agoI think some of us (most? all?) develop a tendency to act/be clever instead of act/be clear. When I resist that temptation, I ask for something like: clamped(num, range=[ lower_bound, upper_bound ]); and then have no interest in how this actually gets implemented.
- gowld 6y agoIf you are going to call a library function, just call median().
- dfabulich 6y agoBeware that in JavaScript, the language that this tweet is about, the sort function sorts alphabetically by default. [100, 10, 11].sort()[1] === 100
- earthboundkid 6y agoWait, really? BRB, just checking some code…
- astrod 6y agoYep, the sort method converts values to strings before comparing. https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/sort https://developer.mozilla.org/en-US/docs/Web/JavaScript/Refe...
- kabacha 6y agoMost popular programming language folks. You give it 3 numbers and it treats them as 3 strings of characters...
- zwaps 6y agoI was confused why the author claims this doesn't work, then I saw JavaScript... ah
- shepherdjerred 6y agoohh this is clever!