Performance optimization for minElement and maxElement

[H. S. Teoh]

On Mon, Sep 12, 2022 at 10:15:45AM -0400, Steven Schveighoffer via Digitalmars-d wrote:
> On 9/12/22 7:53 AM, Sergey wrote:
> > On Monday, 12 September 2022 at 11:46:23 UTC, Ali Çehreli wrote:
> > > 
> > > I am not that silly. :) What I meant is "as soon as they see e.g.
> > > 0". Say, at the third element of a million-element range...
> > > 
> > 
> > In case zero will be the last element - the search should make an
> > extra comparisons “if currentElement = T.minimum” which double
> > operations..  Isn’t it?
> 
> It could only make comparisons when assigning the "current minimum". I
> don't think it would cost that much. Complexity would be the same
> anyway.
> 
> 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.
> 
> 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. And in other cases, the
> enum truly may just be an enum, where the `.max` value is the maximum
> value, but you'd have to defensively check for the max representable
> value, making it perform this check for no reason.

I would on principle exclude enums from this optimization.

Besides, enums as bitfields IMO are a code smell; there really should be
an "official" bitflags type constructor that takes an enum and creates a
bitfield type based on that enum. The constructed type would have .min
and .max appropriately defined as 0 and the bitwise OR of all flags,
respectively.


> A possibility is to provide an overload that accepts the absolute
> minimum or maximum, and only then does it do the extra comparisons.
[...]

Please don't. This smells like one of those well-intentioned extensions
that 5 years later will have us wondering "how did Phobos become this
hairy?".


T

-- 
Debian GNU/Linux: Cray on your desktop.