[
https://issues.apache.org/jira/browse/STDCXX-226?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel#action_12550775
]
Martin Sebor commented on STDCXX-226:
-------------------------------------
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,
PA-RISC, 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: STDCXX-226
> URL: https://issues.apache.org/jira/browse/STDCXX-226
> 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.
