Performance optimization for minElement and maxElement (page 2)

September 12, 2022

Re: Performance optimization for minElement and maxElement

Posted by JG
in reply to Paul Backus

Permalink

Posted in reply to Paul Backus

Permalink

On Monday, 12 September 2022 at 16:26:01 UTC, Paul Backus wrote:

On Monday, 12 September 2022 at 15:27:25 UTC, Steven Schveighoffer wrote:

This isn't that crazy though. Checking against an absolute minimum or maximum has a cost, one which you may not want to incur.

For instance, uint.min is 0, this might be a common occurrence in some ranges. But int.min is -2billion. That might never occur in some ranges. Why waste time checking for something that will never occur in the name of "performance"? For many types and data sets, this is a net pessimization.

And there's not a way to do this shortcut via type wrapping. The only option is to alter the algorithm. Making it opt-in isn't a bad idea, but of course, the API could be badly designed.

It seems like maybe what's desired here is a version of fold that allows for early termination. Like, instead of just returning the next accumulator value, the callback could return a tuple of the next value and a bool continue, or something.

Could build it like this (not sure performance is great).

import std;

auto stoppingFold(alias stopCond, alias op, R)(R r) {
    return r.cumulativeFold!op.until!(stopCond)(No.openRight).fold!((a,b)=>b);
}

void main() {
    auto x = [1,2,4,3];
    assert(x.stoppingFold!(x=>x==0,(a,b)=>min(a,b))==1);
    x = [1,0,4,3];
    assert(x.stoppingFold!(x=>x==0,(a,b)=>min(a,b))==1);
}

import std; auto stoppingFold(alias stopCond, alias op, R)(R r) { return r.cumulativeFold!op.until!(stopCond)(No.openRight).fold!((a,b)=>b); } void main() { auto x = [1,2,4,3]; assert(x.stoppingFold!(x=>x==0,(a,b)=>min(a,b))==1); x = [1,0,4,3]; assert(x.stoppingFold!(x=>x==0,(a,b)=>min(a,b))==1); }

On Monday, 12 September 2022 at 14:15:45 UTC, Steven Schveighoffer wrote:

On 9/12/22 7:53 AM, Sergey wrote:
One thing that is worrisome though, is the fact that min and max aren't always the minimum and maximum bit patterns available. So short-cutting the search might do something you don't want.

Are they only broken for enum?

e.g. an enum which defines a bitfield might have values of 1, 2, 4, 8, but instances of the enum might go all the way up to 15 (all bits set). However, the .max value would be 8.

Actually dmd allows other operations besides | and & on enum members:

enum E
{
	a,
	b=5,
	c=2
}
pragma(msg, E.max); // E.b

immutable E e = E.b << 1;
pragma(msg, e); // cast(E)10

immutable E f = E.b + E.b + E.b;
pragma(msg, f); // cast(E)15

All bits set for E would be 7. I don't know why those operations are allowed.

On 9/12/22 08:27, Steven Schveighoffer wrote: > For instance, uint.min is 0, this might be a common occurrence in some > ranges. But int.min is -2billion. That might *never* occur in some > ranges. Makes sense. My mind caught this "optimization" (if at all) on unsigned types being 0. So I started writing the original post on unsigned types but generalized to all fundamental types as an afterthought. Even maxElement was added by generalization... :) Yeah, I think this is about unsigned and 0. Ali

Forums