Feature #9118

In Enumerable#to_a, use size to set array capa when possible

Added by Aaron Weiner over 1 year ago. Updated about 2 months ago.

[ruby-core:58378]
Status:Closed
Priority:Normal
Assignee:-

Description

Cross-post from https://github.com/ruby/ruby/pull/444.

Enumerable#to_a works by creating an empty array with small capacity, then populating it and expanding the capacity as it goes. For large enumerables, this causes several resizes, which can hurt performance. When an enumerable exposes a size method, we can guess that the resulting array's size will usually be equal to the enumerable's size. If we're right, we only have to set capacity once, and if we're wrong, we don't lose anything.

The attached file (or linked PR) adjusts enum.c's to_a method to take advantage of the size method when it's there. In my tests this makes Range#to_a about 10% faster, and doesn't have any significant effect on a vanilla enum with no size method. I couldn't find any existing benchmark that this consistently made better or worse.

If you like this idea, this could also be done in other classes with custom to_a, like Hash.

enum.c Magnifier - enum.c with modified enum_to_a (72.4 KB) Aaron Weiner, 11/16/2013 11:09 PM


Related issues

Related to Ruby trunk - Bug #11130: Re: [ruby-changes:38376] glass:r50457 (trunk): * enum.c (enum_to_a): Use size to set array capa when possible. Closed

Associated revisions

Revision 50483
Added by glass about 2 months ago

  • enum.c (enum_to_a): revert r50457. it requires recursion check. then, it doesn't make performance improvement. [Bug #11130] [Feature #9118]

History

#1 Updated by Hans Mackowiak over 1 year ago

enum.size can return Float::Infinity maybe for [1,2,3].cycle.size you need to check that too

#2 Updated by Aaron Weiner over 1 year ago

Ah, right! This seems like an opportunity to improve on existing behavior: right now that just silently hangs forever. Do you think we should warn, then hang, or just raise? I'd lean towards the warn because it's possible size is returning the wrong thing.

#3 Updated by Yusuke Endoh over 1 year ago

I think the proposal will break the compatibility of the following code:

class C
include Enumerable
def size
to_a.size
end
def each
end
end
C.new.size #=> expected: 0, with the proposal: stack level too deep

Examples in the wild:

In addition, #each and #size does not necessarily have a common semantics.
In fact, IO#each yields strings in lines, but IO#size returns a count in bytes.

Yusuke Endoh mame@tsg.ne.jp

#4 Updated by Aaron Weiner over 1 year ago

It definitely breaks that usage, but that's bad usage--we're supposed to use Enumerable#count for that, not size.

In cases where size doesn't correctly predict the array, this doesn't really break anything, it just switches out one bad guess at capa for another.

#5 Updated by Hans Mackowiak over 1 year ago

Enumerable#count may not a good idea, better would be Enumerator#size

#6 Updated by Usaku NAKAMURA about 2 months ago

  • Related to Bug #11130: Re: [ruby-changes:38376] glass:r50457 (trunk): * enum.c (enum_to_a): Use size to set array capa when possible. added

#7 Updated by Anonymous about 2 months ago

  • Status changed from Open to Closed

Applied in changeset r50483.


  • enum.c (enum_to_a): revert r50457. it requires recursion check. then, it doesn't make performance improvement. [Bug #11130] [Feature #9118]

Also available in: Atom PDF