Strange Queue.Enqueue(T item) code

Question

While reflecting with ILSpy i found this line of code in the Queue<T>.Enqueue(T item)-method:

if (this._size == this._array.Length)
{
    int num = (int)((long)this._array.Length * 200L / 100L);
    if (num < this._array.Length + 4)
    {
        num = this._array.Length + 4;
    }
    this.SetCapacity(num);
}

I'm just wondering why somebody would do this? I think it's some kind of a integer overflow check, but why multiply first with 200L and then divide by 100L?

Might this have been a issue with earlier compilers?

It can't be related to overflow, since `(long)_array.Length * 200` will never overflow. The `+ 4` stuff is to ensure that the array still grows even if its original size is zero. — Marcelo Cantos, Mar 23 '12 at 11:09
@C.Evenhuis But it's const, so the compiler could optimize it. As i said in the question i think this might be a issue with earlier compilers. — Felix K., Mar 23 '12 at 11:10
@MarceloCantos I didn't mean the `* 200L`, i mean the conversion into long and than back to int. — Felix K., Mar 23 '12 at 11:11
@FelixK.: There's probably no checking going on here. The cast to long merely ensures that `...*200/100` doesn't overflow, and the cast to int is there simply because `num` is defined as `int`. — Marcelo Cantos, Mar 23 '12 at 11:15
@FelixK. If I copy paste that code into VS2008, it does not optimize the *200/100 into *2. — C.Evenhuis, Mar 23 '12 at 11:18
@C.Evenhuis I tested it right now, and you are correct. seems that the compiler isn't optimizing it. Maybe you could add this to your answer. — Felix K., Mar 23 '12 at 11:22

score 4 · Answer 1 · edited May 23 '17 at 11:59

4

Below are all the same and will generate the same result:

int size = (int)((length * 200L) / 100L);
int size = length << 1;
int size = length * 2;

The reason for choosing the first option over the other is to show your intend clearly:

const long TotalArraySize = 200L;
const long BytesPerElement = 100L;
return (length * TotalArraySize) / BytesPerElement;

Some details about performance implications are given here: Doubling a number - shift left vs. multiplication

edited May 23 '17 at 11:59

Community

1
1

answered Mar 23 '12 at 11:09

Teoman Soygul

25,584
6
69
80

3

Are you sure that promoting `length` to `long`, then performing a long multiply followed by a long divide actually qualifies as a performance optimization? – Frédéric Hamidi Mar 23 '12 at 11:12
@TeomanSoygul Your answer is not wrong, but it's still the question why the compiler doesn't optimize `200L / 100L`. – Felix K. Mar 23 '12 at 11:23

C.Evenhuis · Accepted Answer · 2012-03-23T11:20:35.487

Usually things first multiplied then divided by 100 are percentage calculations - Perhaps there was some const XxxPercentage = 200 or something like that in the original code. The compiler does not seem to optimize the * 200 / 100 to * 2.

This code sets the capacity to twice its size - but if twice its size would be smaller than the original size + 4, use that instead.

The reason it is converted to long probably is because if you multiply an integer by the "200 percent" it would overflow.

score 4 · Answer 3 · answered Mar 23 '12 at 11:58

If you continue looking to Queue implementation, you will find following fields:

const int _GrowFactor = 200;
const int _MinimumGrow = 4;

Interesting point is that those constants not used :) I think those constants were hardcoded instead (grow factor also replaced by long type). Lets look for Enqueue method from this point of view:

if (this._size == this._array.Length)
{
    int capacity = (int)((this._array.Length * _GrowFactor) / 100L);
    if (capacity < (this._array.Length + _MinimumGrow))
    {
        capacity = this._array.Length + _MinimumGrow;
    }
    this.SetCapacity(capacity);
}

I think those names make sense. GrowFactor specifies in percents how much array should grow. This is 200% by default. But they also specified minimum grow for internal array. So, if array didn't grow so much as current length + minimum grow, we give this minimal grow anyway.

Maciej · Answer 4 · 2012-03-23T15:33:14.023

Intent of * 200L / 100L is not any more clearer than * 2 in my opinion. The only reason I can think of why it is done like that is to make sure queue length can grow up to 200 times. There is difference in * 200 / 100 and * 2 such that the first one will result in an overflow exception for 100 times smaller number. For example if it was for byte values, x * 200 / 100 would fail for x==2 but * 2 would fail only if x was as big as 128.

But as Marcelo Cantos pointed out (long)this._array.Length * 200L / 100L will never overflow so my answer is probably not helping much.

Can it be a 'feature' of ILSpy? Maybe in source code it is just * 2.

EDIT

After additional investigation it looks that this strange code must be an artefact of some refactoring. I have checked how it's done in List<>

private void EnsureCapacity(int min)
{
    if (this._items.Length < min)
    {
        int num = (this._items.Length == 0) ? 4 : (this._items.Length * 2);
        if (num < min)
        {
            num = min;
        }
        this.Capacity = num;
    }
}

It is as straightforward as you would expect. My guess is that Queue.Enqueue code was reworked but not fully cleaned up and some strange code resulted out of this change. Most developers assume that Microsoft libraries are perfect and everything has a meaning but it is quite likely that not every line of code is written by a genius :-)

Strange Queue.Enqueue(T item) code

4 Answers4