Repository: python-babel/babel
Pull request #272 (2015-10-09 21:20:15)

Faster rounding
At work, we had some performance issues when trying to format almost 100,000 prices in a single report.  Some profiling revelaed inefficiencies in the number rounding functions.  Such number rounding operations can be implemented making use of the `decimal` standard Python module.  Which probably means that the number rounding code in Babel was meant to support Python versions below 2.4.

Since the oldest supported version now is 2.6, it is probably time to remove the rust and make more use of the standard library (when compatibility is not an issue).

Moreover, this pull request also contains some additional code to make use of the `cdecimal` implementation when available (already shipped with Python since 3.3).  Which speeds up some operations considerably.  Here are some dumb microbenchmarks taken with CPython 2.7.

Original rounding implementation:

```
In [4]: %timeit format_currency(1234.5678, 'USD', locale='en_US')
1000 loops, best of 3: 284 µs per loop
```

New rounding implementation based on `decimal`:

```
In [4]: %timeit format_currency(1234.5678, 'USD', locale='en_US')
1000 loops, best of 3: 229 µs per loop
```

New rounding implementation based on `cdecimal`:

```
In [4]: %timeit format_currency(1234.5678, 'USD', locale='en_US')
10000 loops, best of 3: 100 µs per loop
```

This will also make it easier to provide a solution to #90.  However, the API design for that will have to be discussed a bit.


codecov-io: ## [Current coverage][1] is `83.19%`
> Merging **#272** into **master** will decrease coverage by **-0.25%** as of [`6cd9e5b`][3]


```diff
@@            master    #272   diff @@
======================================
  Files           21      21       
  Stmts         3794    3738    -56
  Branches         0       0       
  Methods          0       0       
======================================
- Hit           3166    3110    -56
  Partial          0       0       
  Missed         628     628       
```

> Review entire [Coverage Diff][4] as of [`6cd9e5b`][3]


[1]: https://codecov.io/github/python-babel/babel?ref=6cd9e5bb28a3c7820633280e15486ab84e4886fb
[2]: https://codecov.io/github/python-babel/babel/features/suggestions?ref=6cd9e5bb28a3c7820633280e15486ab84e4886fb
[3]: https://codecov.io/github/python-babel/babel/commit/6cd9e5bb28a3c7820633280e15486ab84e4886fb
[4]: https://codecov.io/github/python-babel/babel/compare/560ce9d0ab7b6dedbd7a3478a3f0a33ffce5dd97...6cd9e5bb28a3c7820633280e15486ab84e4886fb

> Powered by [Codecov](https://codecov.io). Updated on successful CI builds.
erickwilder: Well, honestly I do like pull requests that [removes more code rather than add](https://www.youtube.com/watch?v=oHcToNCn4K8). But I see that there's only a unused test case being removed here (`bankersround()` function is gone) - but you've chaged `parse_grouping()` function a lot. I'm wondering if it's not worth adding some unit tests just to `parse_grouping()` function, since the `bankersround()` function had tests dedicated just to it.

I know that you're indirectly testing it by showing that the behaviour of the library hasn't changed - but I see that adding those tests could prevent some regressions in the future.

Nice work here!

Patch:
diff --git a/.travis.yml b/.travis.yml
index c7a79b1..d25ad5f 100644
--- a/.travis.yml
+++ b/.travis.yml
@@ -11,8 +11,16 @@ matrix:
   include:
     - os: linux
       python: 2.6
+    - os: linux
+      python: 2.6
+      env:
+      - CDECIMAL=cdecimal
     - os: linux
       python: 2.7
+    - os: linux
+      python: 2.7
+      env:
+      - CDECIMAL=cdecimal
     - os: linux
       python: pypy
     - os: linux
@@ -25,12 +33,26 @@ matrix:
       - PYTHON_VERSION=2.6.6
       - PYENV_ROOT=~/.pyenv
       - PATH=$PYENV_ROOT/shims:$PATH:$PYENV_ROOT/bin
+    - os: osx
+      language: generic
+      env:
+      - PYTHON_VERSION=2.6.6
+      - PYENV_ROOT=~/.pyenv
+      - PATH=$PYENV_ROOT/shims:$PATH:$PYENV_ROOT/bin
+      - CDECIMAL=cdecimal
+    - os: osx
+      language: generic
+      env:
+      - PYTHON_VERSION=2.7.10
+      - PYENV_ROOT=~/.pyenv
+      - PATH=$PYENV_ROOT/shims:$PATH:$PYENV_ROOT/bin
     - os: osx
       language: generic
       env:
       - PYTHON_VERSION=2.7.10
       - PYENV_ROOT=~/.pyenv
       - PATH=$PYENV_ROOT/shims:$PATH:$PYENV_ROOT/bin
+      - CDECIMAL=cdecimal
     - os: osx
       language: generic
       env:
@@ -53,7 +75,7 @@ matrix:
 install:
   - bash .ci/deps.${TRAVIS_OS_NAME}.sh
   - pip install --upgrade pip
-  - pip install pytest pytest-cov
+  - pip install --allow-external cdecimal pytest pytest-cov $CDECIMAL
   - pip install --editable .
 
 script:
diff --git a/babel/_compat.py b/babel/_compat.py
index 0f7640d..78cd35a 100644
--- a/babel/_compat.py
+++ b/babel/_compat.py
@@ -54,3 +54,22 @@ else:
 
 
 number_types = integer_types + (float,)
+
+
+#
+# Use cdecimal when available
+#
+from decimal import (Decimal as _dec,
+                     InvalidOperation as _invop,
+                     ROUND_HALF_EVEN as _RHE)
+try:
+    from cdecimal import (Decimal as _cdec,
+                          InvalidOperation as _cinvop,
+                          ROUND_HALF_EVEN as _CRHE)
+    Decimal = _cdec
+    InvalidOperation = (_invop, _cinvop)
+    ROUND_HALF_EVEN = _CRHE
+except ImportError:
+    Decimal = _dec
+    InvalidOperation = _invop
+    ROUND_HALF_EVEN = _RHE
diff --git a/babel/numbers.py b/babel/numbers.py
index af9413f..a15f399 100644
--- a/babel/numbers.py
+++ b/babel/numbers.py
@@ -18,13 +18,11 @@
 # TODO:
 #  Padding and rounding increments in pattern:
 #  - http://www.unicode.org/reports/tr35/ (Appendix G.6)
-from decimal import Decimal, InvalidOperation
-import math
 import re
 from datetime import date as date_, datetime as datetime_
 
 from babel.core import default_locale, Locale, get_global
-from babel._compat import range_type
+from babel._compat import range_type, Decimal, InvalidOperation, ROUND_HALF_EVEN
 
 
 LC_NUMERIC = default_locale('LC_NUMERIC')
@@ -455,94 +453,6 @@ SUFFIX_PATTERN = r"(?P<suffix>.*)"
 number_re = re.compile(r"%s%s%s" % (PREFIX_PATTERN, NUMBER_PATTERN,
                                     SUFFIX_PATTERN))
 
-def split_number(value):
-    """Convert a number into a (intasstring, fractionasstring) tuple"""
-    if isinstance(value, Decimal):
-        # NB can't just do text = str(value) as str repr of Decimal may be
-        # in scientific notation, e.g. for small numbers.
-
-        sign, digits, exp = value.as_tuple()
-        # build list of digits in reverse order, then reverse+join
-        # as per http://docs.python.org/library/decimal.html#recipes
-        int_part = []
-        frac_part = []
-
-        digits = list(map(str, digits))
-
-        # get figures after decimal point
-        for i in range(-exp):
-            # add digit if available, else 0
-            if digits:
-                frac_part.append(digits.pop())
-            else:
-                frac_part.append('0')
-
-        # add in some zeroes...
-        for i in range(exp):
-            int_part.append('0')
-
-        # and the rest
-        while digits:
-            int_part.append(digits.pop())
-
-        # if < 1, int_part must be set to '0'
-        if len(int_part) == 0:
-            int_part = '0',
-
-        if sign:
-            int_part.append('-')
-
-        return ''.join(reversed(int_part)), ''.join(reversed(frac_part))
-    text = ('%.9f' % value).rstrip('0')
-    if '.' in text:
-        a, b = text.split('.', 1)
-        if b == '0':
-            b = ''
-    else:
-        a, b = text, ''
-    return a, b
-
-
-def bankersround(value, ndigits=0):
-    """Round a number to a given precision.
-
-    Works like round() except that the round-half-even (banker's rounding)
-    algorithm is used instead of round-half-up.
-
-    >>> bankersround(5.5, 0)
-    6.0
-    >>> bankersround(6.5, 0)
-    6.0
-    >>> bankersround(-6.5, 0)
-    -6.0
-    >>> bankersround(1234.0, -2)
-    1200.0
-    """
-    sign = int(value < 0) and -1 or 1
-    value = abs(value)
-    a, b = split_number(value)
-    digits = a + b
-    add = 0
-    i = len(a) + ndigits
-    if i < 0 or i >= len(digits):
-        pass
-    elif digits[i] > '5':
-        add = 1
-    elif digits[i] == '5' and digits[i-1] in '13579':
-        add = 1
-    elif digits[i] == '5':     # previous digit is even
-        # We round up unless all following digits are zero.
-        for j in range_type(i + 1, len(digits)):
-            if digits[j] != '0':
-                add = 1
-                break
-
-    scale = 10**ndigits
-    if isinstance(value, Decimal):
-        return Decimal(int(value * scale + add)) / scale * sign
-    else:
-        return float(int(value * scale + add)) / scale * sign
-
 
 def parse_grouping(p):
     """Parse primary and secondary digit grouping
@@ -645,35 +555,30 @@ class NumberPattern(object):
         self.exp_prec = exp_prec
         self.exp_plus = exp_plus
         if '%' in ''.join(self.prefix + self.suffix):
-            self.scale = 100
+            self.scale = 2
         elif u'‰' in ''.join(self.prefix + self.suffix):
-            self.scale = 1000
+            self.scale = 3
         else:
-            self.scale = 1
+            self.scale = 0
 
     def __repr__(self):
         return '<%s %r>' % (type(self).__name__, self.pattern)
 
     def apply(self, value, locale, currency=None, force_frac=None):
         frac_prec = force_frac or self.frac_prec
-        if isinstance(value, float):
+        if not isinstance(value, Decimal):
             value = Decimal(str(value))
-        value *= self.scale
-        is_negative = int(value < 0)
+        value = value.scaleb(self.scale)
+        is_negative = int(value.is_signed())
         if self.exp_prec: # Scientific notation
+            exp = value.adjusted()
             value = abs(value)
-            if value:
-                exp = int(math.floor(math.log(value, 10)))
-            else:
-                exp = 0
             # Minimum number of integer digits
             if self.int_prec[0] == self.int_prec[1]:
                 exp -= self.int_prec[0] - 1
             # Exponent grouping
             elif self.int_prec[1]:
                 exp = int(exp / self.int_prec[1]) * self.int_prec[1]
-            if not isinstance(value, Decimal):
-                value = float(value)
             if exp < 0:
                 value = value * 10**(-exp)
             else:
@@ -685,29 +590,25 @@ class NumberPattern(object):
                 exp_sign = get_plus_sign_symbol(locale)
             exp = abs(exp)
             number = u'%s%s%s%s' % \
-                 (self._format_sigdig(value, frac_prec[0], frac_prec[1]),
+                 (self._format_significant(value, frac_prec[0], frac_prec[1]),
                   get_exponential_symbol(locale),  exp_sign,
                   self._format_int(str(exp), self.exp_prec[0],
                                    self.exp_prec[1], locale))
         elif '@' in self.pattern: # Is it a siginificant digits pattern?
-            text = self._format_sigdig(abs(value),
-                                      self.int_prec[0],
-                                      self.int_prec[1])
-            if '.' in text:
-                a, b = text.split('.')
-                a = self._format_int(a, 0, 1000, locale)
-                if b:
-                    b = get_decimal_symbol(locale) + b
-                number = a + b
-            else:
-                number = self._format_int(text, 0, 1000, locale)
+            text = self._format_significant(abs(value),
+                                            self.int_prec[0],
+                                            self.int_prec[1])
+            a, sep, b = text.partition(".")
+            number = self._format_int(a, 0, 1000, locale)
+            if sep:
+                number += get_decimal_symbol(locale) + b
         else: # A normal number pattern
-            a, b = split_number(bankersround(abs(value), frac_prec[1]))
-            b = b or '0'
-            a = self._format_int(a, self.int_prec[0],
-                                 self.int_prec[1], locale)
-            b = self._format_frac(b, locale, force_frac)
-            number = a + b
+            precision = Decimal('1.' + '1' * frac_prec[1])
+            rounded = value.quantize(precision, ROUND_HALF_EVEN)
+            a, sep, b = str(abs(rounded)).partition(".")
+            number = (self._format_int(a, self.int_prec[0],
+                                       self.int_prec[1], locale) +
+                      self._format_frac(b or '0', locale, force_frac))
         retval = u'%s%s%s' % (self.prefix[is_negative], number,
                                 self.suffix[is_negative])
         if u'¤' in retval:
@@ -717,31 +618,44 @@ class NumberPattern(object):
             retval = retval.replace(u'¤', get_currency_symbol(currency, locale))
         return retval
 
-    def _format_sigdig(self, value, min, max):
-        """Convert value to a string.
-
-        The resulting string will contain between (min, max) number of
-        significant digits.
-        """
-        a, b = split_number(value)
-        ndecimals = len(a)
-        if a == '0' and b != '':
-            ndecimals = 0
-            while b.startswith('0'):
-                b = b[1:]
-                ndecimals -= 1
-        a, b = split_number(bankersround(value, max - ndecimals))
-        digits = len((a + b).lstrip('0'))
-        if not digits:
-            digits = 1
-        # Figure out if we need to add any trailing '0':s
-        if len(a) >= max and a != '0':
-            return a
-        if digits < min:
-            b += ('0' * (min - digits))
-        if b:
-            return '%s.%s' % (a, b)
-        return a
+    #
+    # This is one tricky piece of code.  The idea is to rely as much as possible
+    # on the decimal module to minimize the amount of code.
+    #
+    # Conceptually, the implementation of this method can be summarized in the
+    # following steps:
+    #
+    #   - Move or shift the decimal point (i.e. the exponent) so the maximum
+    #     amount of significant digits fall into the integer part (i.e. to the
+    #     left of the decimal point)
+    #
+    #   - Round the number to the nearest integer, discarding all the fractional
+    #     part which contained extra digits to be eliminated
+    #
+    #   - Convert the rounded integer to a string, that will contain the final
+    #     sequence of significant digits already trimmed to the maximum
+    #
+    #   - Restore the original position of the decimal point, potentially
+    #     padding with zeroes on either side
+    #
+    def _format_significant(self, value, minimum, maximum):
+        exp = value.adjusted()
+        scale = maximum - 1 - exp
+        digits = str(value.scaleb(scale).quantize(Decimal(1), ROUND_HALF_EVEN))
+        if scale <= 0:
+            result = digits + '0' * -scale
+        else:
+            intpart = digits[:-scale]
+            i = len(intpart)
+            j = i + max(minimum - i, 0)
+            result = "{intpart}.{pad:0<{fill}}{fracpart}{fracextra}".format(
+                    intpart=intpart or '0',
+                    pad='',
+                    fill=-min(exp + 1, 0),
+                    fracpart=digits[i:j],
+                    fracextra=digits[j:].rstrip('0'),
+            ).rstrip('.')
+        return result
 
     def _format_int(self, value, min, max, locale):
         width = len(value)
diff --git a/babel/plural.py b/babel/plural.py
index 50bf541..b5ce9ba 100644
--- a/babel/plural.py
+++ b/babel/plural.py
@@ -8,10 +8,11 @@
     :copyright: (c) 2013 by the Babel Team.
     :license: BSD, see LICENSE for more details.
 """
-import decimal
 import re
 import sys
 
+from babel._compat import Decimal
+
 
 _plural_tags = ('zero', 'one', 'two', 'few', 'many', 'other')
 _fallback_tag = 'other'
@@ -32,9 +33,9 @@ def extract_operands(source):
             # 2.6's Decimal cannot convert from float directly
             if sys.version_info < (2, 7):
                 n = str(n)
-            n = decimal.Decimal(n)
+            n = Decimal(n)
 
-    if isinstance(n, decimal.Decimal):
+    if isinstance(n, Decimal):
         dec_tuple = n.as_tuple()
         exp = dec_tuple.exponent
         fraction_digits = dec_tuple.digits[exp:] if exp < 0 else ()
diff --git a/tox.ini b/tox.ini
index 311da6e..a5b23e4 100644
--- a/tox.ini
+++ b/tox.ini
@@ -1,8 +1,11 @@
 [tox]
-envlist = py26, py27, pypy, py33, py34
+envlist = py26, py27, pypy, py33, py34, py26-cdecimal, py27-cdecimal
 
 [testenv]
+install_command =
+    pip install --allow-external cdecimal {opts} {packages}
 deps =
     pytest
+    cdecimal: cdecimal
 whitelist_externals = make
 commands = make clean-cldr test


Test patch:
diff --git a/tests/test_numbers.py b/tests/test_numbers.py
index a773f48..f042833 100644
--- a/tests/test_numbers.py
+++ b/tests/test_numbers.py
@@ -11,13 +11,13 @@
 # individuals. For the exact contribution history, see the revision
 # history and logs, available at http://babel.edgewall.org/log/.
 
-from decimal import Decimal
 import unittest
 import pytest
 
 from datetime import date
 
 from babel import numbers
+from babel._compat import Decimal
 
 
 class FormatDecimalTestCase(unittest.TestCase):
@@ -151,19 +151,6 @@ class FormatDecimalTestCase(unittest.TestCase):
         self.assertEqual('0.000000700', fmt)
 
 
-class BankersRoundTestCase(unittest.TestCase):
-    def test_round_to_nearest_integer(self):
-        self.assertEqual(1, numbers.bankersround(Decimal('0.5001')))
-
-    def test_round_to_even_for_two_nearest_integers(self):
-        self.assertEqual(0, numbers.bankersround(Decimal('0.5')))
-        self.assertEqual(2, numbers.bankersround(Decimal('1.5')))
-        self.assertEqual(-2, numbers.bankersround(Decimal('-2.5')))
-
-        self.assertEqual(0, numbers.bankersround(Decimal('0.05'), ndigits=1))
-        self.assertEqual(Decimal('0.2'), numbers.bankersround(Decimal('0.15'), ndigits=1))
-
-
 class NumberParsingTestCase(unittest.TestCase):
     def test_can_parse_decimals(self):
         self.assertEqual(Decimal('1099.98'),
@@ -284,6 +271,8 @@ def test_format_currency_format_type():
 
 def test_format_percent():
     assert numbers.format_percent(0.34, locale='en_US') == u'34%'
+    assert numbers.format_percent(0.34, u'##0%', locale='en_US') == u'34%'
+    assert numbers.format_percent(34, u'##0', locale='en_US') == u'34'
     assert numbers.format_percent(25.1234, locale='en_US') == u'2,512%'
     assert (numbers.format_percent(25.1234, locale='sv_SE')
             == u'2\xa0512\xa0%')
@@ -320,13 +309,6 @@ def test_parse_decimal():
     assert excinfo.value.args[0] == "'2,109,998' is not a valid decimal number"
 
 
-def test_bankersround():
-    assert numbers.bankersround(5.5, 0) == 6.0
-    assert numbers.bankersround(6.5, 0) == 6.0
-    assert numbers.bankersround(-6.5, 0) == -6.0
-    assert numbers.bankersround(1234.0, -2) == 1200.0
-
-
 def test_parse_grouping():
     assert numbers.parse_grouping('##') == (1000, 1000)
     assert numbers.parse_grouping('#,###') == (3, 3)
diff --git a/tests/test_plural.py b/tests/test_plural.py
index 278b5db..b0cad8d 100644
--- a/tests/test_plural.py
+++ b/tests/test_plural.py
@@ -10,10 +10,11 @@
 # This software consists of voluntary contributions made by many
 # individuals. For the exact contribution history, see the revision
 # history and logs, available at http://babel.edgewall.org/log/.
-import decimal
 import unittest
 import pytest
+
 from babel import plural
+from babel._compat import Decimal
 
 
 def test_plural_rule():
@@ -33,29 +34,29 @@ def test_plural_rule_operands_i():
 
 def test_plural_rule_operands_v():
     rule = plural.PluralRule({'one': 'v is 2'})
-    assert rule(decimal.Decimal('1.20')) == 'one'
-    assert rule(decimal.Decimal('1.2')) == 'other'
+    assert rule(Decimal('1.20')) == 'one'
+    assert rule(Decimal('1.2')) == 'other'
     assert rule(2) == 'other'
 
 
 def test_plural_rule_operands_w():
     rule = plural.PluralRule({'one': 'w is 2'})
-    assert rule(decimal.Decimal('1.23')) == 'one'
-    assert rule(decimal.Decimal('1.20')) == 'other'
+    assert rule(Decimal('1.23')) == 'one'
+    assert rule(Decimal('1.20')) == 'other'
     assert rule(1.2) == 'other'
 
 
 def test_plural_rule_operands_f():
     rule = plural.PluralRule({'one': 'f is 20'})
-    assert rule(decimal.Decimal('1.23')) == 'other'
-    assert rule(decimal.Decimal('1.20')) == 'one'
+    assert rule(Decimal('1.23')) == 'other'
+    assert rule(Decimal('1.20')) == 'one'
     assert rule(1.2) == 'other'
 
 
 def test_plural_rule_operands_t():
     rule = plural.PluralRule({'one': 't = 5'})
-    assert rule(decimal.Decimal('1.53')) == 'other'
-    assert rule(decimal.Decimal('1.50')) == 'one'
+    assert rule(Decimal('1.53')) == 'other'
+    assert rule(Decimal('1.50')) == 'one'
     assert rule(1.5) == 'one'
 
 
@@ -250,6 +251,6 @@ EXTRACT_OPERANDS_TESTS = (
 
 @pytest.mark.parametrize('source,n,i,v,w,f,t', EXTRACT_OPERANDS_TESTS)
 def test_extract_operands(source, n, i, v, w, f, t):
-    source = decimal.Decimal(source) if isinstance(source, str) else source
+    source = Decimal(source) if isinstance(source, str) else source
     assert (plural.extract_operands(source) ==
-            decimal.Decimal(n), i, v, w, f, t)
+            Decimal(n), i, v, w, f, t)