7 Replies Latest reply: Mar 29, 2009 5:11 AM by 807557 RSS

    Why no constant time memory allocation?

    807557
      Hi,

      I'm working with RTS 2.1 and trying to understand why allocating memory in ScopedMemory (LTMemory or VTMemory - they both have in our tests linear allocation times) takes that much time. I'm sure there's some clear reason - but I still don't get it.
      Before working with RTS 2.1 I have done some real-time applications in C and C++. The allocation of different memory sizes was always constant. On hardware level it takes just some additions to allocate a new object in memory (setting some pointer to new values). So this additions are more or less always the same, independent of the size of the new object. Where is the difference to allocating memory in ScopedMemory area?

      Thanking you in anticipation.
        • 1. Re: Why no constant time memory allocation?
          807557
          constant-time memory allocation is a goal but not required by the RTSJ - the only mandate linear-time or else variable-time.

          In many case scope allocation can be done in constant time - in fact normal heap allocation can also be constant time if using TLABs and the allocation fits - as it is a simple pointer-bump. But there can be additional activities needed on an allocation that adds to the cost.

          How are you measuring the scope allocation cost? Are you using RTT or NHRT?

          David Holmes
          • 2. Re: Why no constant time memory allocation?
            807557
            Hey David,

            thanks for this helpfull answer!

            I'm measuring the scope allocation costs with a RTT. And both LTMemory and VTMemory have linear allocation times. As long as the allocated size is low, this linear time is absorbable. But thinking of allocating 200 MB or even more, this will take a lot of time.
            In our case we are monitoring many sensors inside a motor. I'ts a lot of data coming through that has to be computed and evaluated in realtime to monitor the system behavior to the operator. After some thounsands of computations the values can be deleted - that's where we we exit a scoped area and enter a new one - and new computations take place.
            • 3. Re: Why no constant time memory allocation?
              807557
              can you show me how you're measuring the allocation time?

              Thanks,
              David Holmes
              • 4. Re: Why no constant time memory allocation?
                807557
                Looks like you may have uncovered a bug. It seems that we're double-zeroing the memory: once when the scope is cleared, then again on each allocation - the latter is why allocation cost is linear in the size of the object.

                David Holmes
                • 5. Re: Why no constant time memory allocation?
                  807557
                  Hey David,

                  this is the way we are allocating ScopedMemory Space:
                  private class ScopeRunnable implements Runnable {
                    ...
                  
                    public void run() {
                      ...
                      rtClock.getTime(timeBeforeAllocation);
                      byte[] array = new byte[someSize];
                      rtClock.getTime(timeAfterAllocation);
                    }
                  } 
                  This runnable is started via:
                  ScopeRunnable runner = new ScopeRunnable();
                  
                  ScopedMemory scope = new LTMemory(enoughSize);
                  
                  scope.enter(runner);
                  I hope this is the right way.

                  Regards
                  • 6. Re: Why no constant time memory allocation?
                    807557
                    It seems that we're double-zeroing the memory: once when the scope is cleared, then again on each allocation - the latter is why allocation cost is linear in the size of the object.
                    Ok but I still don't understand how the latter action leads to a allocation cost linear to the size of the object?

                    Thanks,
                    Gordon
                    • 7. Re: Why no constant time memory allocation?
                      807557
                      Gordon_Realtime wrote:
                      Ok but I still don't understand how the latter action leads to a allocation cost linear to the size of the object?
                      Because the cost of zeroing memory is proportional to the size of memory being zeroed.

                      David