mina-dev mailing list archives

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

    [ https://issues.apache.org/jira/browse/DIRMINA-751?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12787184#action_12787184
] 

Christopher Popp commented on DIRMINA-751:
------------------------------------------

Weird...I tried out the patch and the test and I got the following results on my laptop.

Original

Time for performance test 1: 6313 ms
Time for performance test 2: 6657 ms

with binary search

Time for performance test 1: 5391 ms
Time for performance test 2: 5344 ms


I thought the binary search implementation was a little complicated, so I looked and found
an algorithm on wikipedia (http://en.wikipedia.org/wiki/Power_of_two#Algorithm_to_find_the_next-highest_power_of_two)
and implemented it:

    protected static int normalizeCapacity(int requestedCapacity) {
    		if(requestedCapacity == 0){
    			return 0;
    		} else if(requestedCapacity > 0){
    			requestedCapacity--;
    		}
    		for(int i = 1; i < 32; i<<=1) {
    			requestedCapacity = (requestedCapacity | requestedCapacity >> i);
    		}
    		return (requestedCapacity == Integer.MAX_VALUE) ? Integer.MAX_VALUE : requestedCapacity+1;
    }

the time for this implementation is:

Time for performance test 1: 2000 ms
Time for performance test 2: 1890 ms

So, it would seem as thought at least on my machine it is faster than the other two machines,
but it would be interesting for someone to also try it out and see.



> 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
>
>         Attachments: IoBufferTest.java, patch.txt
>
>
> 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