bugGNU Octave - Bugs: bug #57321, Performance degradation due to...

 
 

bug #57321: Performance degradation due to memory allocation

Submitter:  None
Submitted:  Thu 28 Nov 2019 06:11:45 PM UTC
   
 
Category:  Interpreter Severity:  3 - Normal
Priority:  5 - Normal Item Group:  Performance
Status:  Need Info Assigned to:  None
Originator Name:  Originator Email:  -email is unavailable-
Open/Closed:  * Open Release:  * dev
Operating System:  * Any Fixed Release:  None
Planned Release:  None
* Mandatory Fields

Add a New Comment Rich Markup
   

Jump to the original submission

Mon 09 Dec 2019 07:52:14 PM UTC, comment #7: 

Following up [1] I used "bm.toeplitz"



runs = 1;

cumulate = 0; b = 0;
for i = 1:runs
  b = zeros (620, 620);
  tic;
    for j = 1:620
      for k = 1:620
        b(k,j) = abs (j - k) + 1;
      end
    end
  timing = toc;
  cumulate = cumulate + timing;
end


Instead of compiling Octave I changed libstdc++ to redirect all of its small sized "malloc" and "free" calls to the memory pool. Also because the "thread_local" declaration is ,at least in Windows,inefficient I used a lock-free queue instead of the vector as the internal structure of the memory pool. The performance gain was 40% relative to Octave without memory pool.

[1] https://savannah.gnu.org/bugs/?56752

Anonymous
Sat 07 Dec 2019 08:45:46 PM UTC, comment #6: 

I should correct what I have said in the previous comment. The number 4,800,000 is the number of bytes totally allocated. The number of allocations with "new operator" per iteration is 6 instead of 7000.

Anonymous
Fri 06 Dec 2019 06:18:39 PM UTC, comment #5: 

Consider the following loop:


a = 1;
b = 1;
for k = 1:10
  b = b + a;
end


It can be roughly translate to c++ :



double *a = new double (1);
double *b = new double (1);
for (int k = 1; k <=10; k++)
{
  double *temp = new int(*b + *a);
  *b = *temp;
  delete temp;
}


Each plus operation invokes the memory allocator.
The real number of allocations is far more than this. Using Api Monitor in Windows a loop of 7,000 iterations in Octave results in about 4,800,000 mallocs or about 700 allocations per iteration.

I also attached a test program in c++ that measures the performance of the "plus" operator. Two classes are defined one of them uses the memory pool and the other class uses memory allocation. It can be seen that the memory pool can provide 6X speedup.
I haven't compiled the Octave so I can't say how the memory pool can affect its performance. But I expect it will provide an improvement.
Thanks for your attention!


(file #48018)

Anonymous
Thu 05 Dec 2019 08:06:40 PM UTC, comment #4: 

Thanks for your  bug report. Can you explain what "performance degradation" means? Is the degradation relative to previous versions of Octave, or is it along an Octave session ...?

Can you also provide some concrete measurement of this degradation and of the improvements your changes bring?

Pantxo Diribarne <pantxo>
Group Member
Thu 05 Dec 2019 02:38:52 PM UTC, comment #3: 

I made some changes.
The memory pool is added to each class via a In the file ther is a macro named "DECLARE_OV_TYPEID_FUNCTIONS_AND_DATA2" that currently is used by "octave_base_value" and most of its sub-classes. The macro defines static members like "static type id" and "name". I have changed the macro so it can add the memory pool to each class that use it.
Sometimes a subclass of "octave_base_value" may not use the macro. In such cases the previous design "ov-base3.h" won't be applicable so I changed it and uploaded "ov-base4.h" and "ov-base4.h.diff". I also added the exception safety for the "free" method of the memory pool.

Nearly 60 classes are using the macro so there are 60 memory pools per thread and as octave currently works with at most two threads there are totally 120 memory_pools in "octave_gui" and 60 in "octave_cli".

A sub-class of "octave_base_value" that doesn't use the macro if its size is equal to its parent ,that is using the macro, can benefit from the memory pool of its parent.

So with the current design the memory pools are distributed across classes. An alternative design would be a central memory pool that contains an array of sub pools. I will explain more in a next comment.


(file #48002, file #48003)

Anonymous
Mon 02 Dec 2019 09:18:39 PM UTC, comment #2: 

I have noticed that in addition to the interpreter thread there is at least one thread, octave_gui, that accesses octave objects. So I made the memory pool thread-safe by declaring it as "thread_local". In Linux systems it should be compiled with option "-ftls-model=initial-exec" to achieve high performance [1]. I also changed it to grow on demand.

There are nearly 40 types that inherit "octave_base_value". Each type has its own memory manager. In octave_gui that has two threads there are totally about 80 memory managers (ntypes x nthreads). Each one is lightweight and grow on demand and their size don't exceed 1000 elements. I expect 300% of performance improvement.
I attached "ov-base3.h" and "ov-base3.h.diff"

[1] https://stackoverflow.com/a/40635676/6579744

(file #47968, file #47969)

Anonymous
Fri 29 Nov 2019 04:50:21 AM UTC, comment #1: 

Sorry, I found some problems in the pool implementation so I edited the source. The files "ov-base2.h.diff" and "ov-base2.h" attached are correct.

(file #47944, file #47945)

Anonymous
Thu 28 Nov 2019 06:11:45 PM UTC, original submission:  

Currently performance of octave is affected by extensive memory allocations. I think using a customized memory allocator or a memory pool can improve the performance. For example Python uses a simple free list for allocation of small numeric objects.
I changed the file ov-base.h and implemented a simple free-list based memory pool and provided custom "new" and "delete" operators for the class "octave_base_value". The diff file and the modified file are attached.



Anonymous

 

(Note: upload size limit is set to 16384 kB, after insertion of the required escape characters.)

Attach Files:
   
   
Comment:
   

Attached Files
file #48018:  test_pool.cpp added by None (3KiB - application/octet-stream - simple testing the pool)
file #48002:  ov-base4.h added by None (27KiB - application/octet-stream - memory_pool distributed across classes)
file #48003:  ov-base4.h.diff added by None (5KiB - application/octet-stream - memory_pool distributed across classes)
file #47968:  ov-base3.h added by None (27KiB - application/octet-stream - thread safe memory manager growing on demand)
file #47969:  ov-base3.h.diff added by None (3KiB - application/octet-stream - thread safe memory manager growing on demand)
file #47944:  ov-base2.h.diff added by None (3KiB - application/octet-stream)
file #47945:  ov-base2.h added by None (27KiB - application/octet-stream)
file #47940:  ov-base.h.diff added by None (3KiB - application/octet-stream)
file #47941:  ov-base1.h added by None (27KiB - application/octet-stream)

 

Depends on the following items: None found

Items that depend on this one: None found

 

Carbon-Copy List
  • -email is unavailable- added by pantxo (Posted a comment)
  •  

    There are 0 votes so far. Votes easily highlight which items people would like to see resolved in priority, independently of the priority of the item set by tracker managers.

    Only group members can vote.

     

    Follow 10 latest changes.

    Date Changed by Updated Field Previous Value => Replaced by
    2019-12-06 None Attached File- Added test_pool.cpp, #48018
    2019-12-05 pantxo StatusNone Need Info
    2019-12-05 None Attached File- Added ov-base4.h, #48002
        Attached File- Added ov-base4.h.diff, #48003
    2019-12-02 None Attached File- Added ov-base3.h, #47968
        Attached File- Added ov-base3.h.diff, #47969
    2019-11-29 None Attached File- Added ov-base2.h.diff, #47944
        Attached File- Added ov-base2.h, #47945
    2019-11-28 None Attached File- Added ov-base.h.diff, #47940
        Attached File- Added ov-base1.h, #47941

    Back to the top

    Powered by Savane 3.13-4448.
    Corresponding source code