mina-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Bogdan Pistol (JIRA)" <j...@apache.org>
Subject [jira] Created: (DIRMINA-751) IoBuffer.normalizeCapacity improvement
Date Mon, 07 Dec 2009 21:08:18 GMT
IoBuffer.normalizeCapacity improvement
--------------------------------------

                 Key: DIRMINA-751
                 URL: https://issues.apache.org/jira/browse/DIRMINA-751
             Project: MINA
          Issue Type: Improvement
          Components: Core
    Affects Versions: 2.0.0-RC1
         Environment: N/A
            Reporter: Bogdan Pistol
            Priority: Minor
             Fix For: 2.0.0-RC1


The technique of computing the minimum power of 2 that is bigger than the requestedCapacity
in the org.apache.mina.core.buffer.IoBuffer.normalizeCapacity() is not optimal.
The current computation is as follows:

 int newCapacity = 1;
        while ( newCapacity < requestedCapacity )  {
            newCapacity <<= 1;
            if ( newCapacity < 0 )   {
                return Integer.MAX_VALUE;
            }
        }

The time complexity of this is O(n), where n is the number of bits of the requestedCapacity
integer, that is log2(requestedCapacity) - maximum 31.
This creates an unnecessary overhead in some high IoBuffer allocations scenarios that are
calling IoBuffer.normalizeCapacity() a lot when creating IoBuffers. I observed this when benchmarking
a MINA server with hprof.
There is a better solution to this problem than to iterate the bits from 0 to log2(requestedCapacity).

The alternative is to use a binary search technique that has optimal time complexity of O(5).
Because requestedCapacity is an integer and has a maximum of 2^5 (32) bits we can binary search
in the set of bits and determine in O(5) comparisons the minimum power of 2 that is bigger
than the requestedCapacity.

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