Mailing-List: contact dev-help@mina.apache.org; run by ezmlm
Precedence: bulk
Reply-To: dev@mina.apache.org
Message-ID: <301374729.1260226098106.JavaMail.jira@brutus>
Date: Mon, 7 Dec 2009 22:48:18 +0000 (UTC)
From: "Christopher Popp (JIRA)" <jira@apache.org>
To: dev@mina.apache.org
Subject: [jira] Issue Comment Edited: (DIRMINA-751)
 IoBuffer.normalizeCapacity improvement
In-Reply-To: <239797445.1260220098177.JavaMail.jira@brutus>
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: 7bit


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

Christopher Popp edited comment on DIRMINA-751 at 12/7/09 10:47 PM:
--------------------------------------------------------------------

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 though at least on my machine it is faster than the other two algorithms, but it would be interesting for someone to also try it out and see.


      was (Author: cpopp):
    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.