[ https://issues.apache.org/jira/browse/STDCXX226?page=com.atlassian.jira.plugin.system.issuetabpanels:commenttabpanel#action_12550775 ]
Martin Sebor commented on STDCXX226:

We still need to benchmark this before making any changes...
Currently, we get the new capacity by multiplying the current value by an approximation of the Golden Ratio (http://en.wikipedia.org/wiki/Golden_ratio), or 1.618:
z = x * 1.618
I suspect that the closest we'll be able to come to this value using integer operations without incurring a significant performance penalty is by multiplying the current value by 16 and dividing the result by 10. We can avoid the expensive division by 10 by approximating the operations using reciprocal multiplication as described below. I.e., like so:
z = x << 4;
z = ((z >> 1) + z) >> 1;
z = ((z >> 4) + z);
z = ((z >> 8) + z);
z = ((z >> 16) + z) >> 3;
http://www.cs.uiowa.edu/~jones/bcd/divide.html
I put together a simple benchmark to compare the performance of the original algorithm to that of the new one. I also included the approach I describe here because it seems to produce results that are closer to the original. The benchmark shows that eliminating the FP operations yields a dramatic improvement (an order of magnitude or more) on all architectures (x86, IA64, PARISC, PowerPC, or SPARC) regardless of which of the two approaches we go with. The algorithm in your patch performs slightly better than the alternative here (between 10% and up to twice as fast, depending on the hardware architecture) but yields results that are considerably less accurate than the alternative (I haven't measured by how much). So unless you think the performance gain is more important, I think we should go with the alternative I presented here.
> __rw::__rw_new_capacity() uses floating point math
> 
>
> Key: STDCXX226
> URL: https://issues.apache.org/jira/browse/STDCXX226
> Project: C++ Standard Library
> Issue Type: Improvement
> Components: 23. Containers
> Affects Versions: 4.1.2, 4.1.3, 4.2.0
> Environment: all
> Reporter: Martin Sebor
> Assignee: Farid Zaripov
> Fix For: 4.2.1
>
> Attachments: new_capacity.patch
>
>
> Moved from the Rogue Wave bug tracking database:
> ****Created By: sebor @ May 09, 2002 11:15:41 AM****
> The template __rw_new_capacity() uses floating point arithmetic which may be less efficient than integer arithmetic on some architectures. Need to change to integer arithmetic and correctly handle integer overflow.

This message is automatically generated by JIRA.

You can reply to this email to add a comment to the issue online.