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