stdcxx-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Martin Sebor (JIRA)" <j...@apache.org>
Subject [jira] Commented: (STDCXX-226) __rw::__rw_new_capacity() uses floating point math
Date Wed, 12 Dec 2007 00:54:43 GMT

    [ 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.


Mime
View raw message