chunkBy implementation

H. S. Teoh hsteoh at quickfur.ath.cx
Tue Sep 29 22:08:58 UTC 2020


On Tue, Sep 29, 2020 at 05:33:35PM -0400, Steven Schveighoffer via Digitalmars-d wrote:
> Here is the chunkBy implementation for an array: https://github.com/dlang/phobos/blob/4d7e5829cb60946fefad84d066de948e813eb6f5/std/algorithm/iteration.d#L2057
> 
> Complete with RefCounted allocations and everything. The whole works!

I was the one who wrote the original (non-RefCounted) implementation of
chunkBy. During PR review, however, we ran into the case of how the
resulting range iterates the original range twice: once in the subranges
as you .popFront through them, and once in the parent range's .popFront
(which needs to find the end of the subrange).

To eliminate this redundancy, Andrei came up with the mothership idea:
the subrange would keep a reference to the parent range, so that if the
subrange has already been consumed, the parent range can just pick up
where it left off instead of starting from the beginning of the subrange
and scan until the next subrange.

Keeping a reference to the parent range, however, opens a whole can o'
worms about lifetime and all that jazz, so in the end, RefCounted was
brought into the mix, to solve what's arguably a case of premature
optimization.


[...]
> Is there a reason we want to call the predicate all over again if you
> process a group multiple times? Is there a reason we aren't taking
> advantage of slicing when available?

I think I was so burned out by the time we arrived at the RefCounted
implementation, I just had no more strength or interest left to think
about the case when the incoming range has slicing!  It's probably a
case of an over-engineered solution displacing all other locally more
optimal solutions -- since the RefCounted monster already handles all
cases, nobody wants to introduce another case into the code that only
handles a subset of cases.


T

-- 
You are only young once, but you can stay immature indefinitely. -- azephrahel


More information about the Digitalmars-d mailing list