Uploaded image for project: 'MINA'
  1. MINA
  2. DIRMINA-751

IoBuffer.normalizeCapacity improvement

    XMLWordPrintableJSON

    Details

    • Type: Improvement
    • Status: Closed
    • Priority: Minor
    • Resolution: Fixed
    • Affects Version/s: 2.0.0-RC1
    • Fix Version/s: 2.0.0
    • Component/s: Core
    • Labels:
      None
    • Environment:
      N/A

      Description

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

        Attachments

        1. patch-lookup-tables.txt
          3 kB
          Bogdan Pistol
        2. patch.txt
          5 kB
          Bogdan Pistol
        3. IoBufferTest.java
          3 kB
          Bogdan Pistol
        4. IoBufferTest.java
          3 kB
          Bogdan Pistol
        5. IoBufferTest.java
          4 kB
          Bogdan Pistol

          Activity

            People

            • Assignee:
              Unassigned
              Reporter:
              bogdan.pistol Bogdan Pistol
            • Votes:
              0 Vote for this issue
              Watchers:
              0 Start watching this issue

              Dates

              • Created:
                Updated:
                Resolved: