Extremely slow std::free() calls.

[DavidPajak]

Description

Recently, I wrote a bunch of gtest unit-test to instrument the image processing library we developed. The unit-test are a standard aarch64 elf64 executable, and the library is a standard dynamic shared library. I push both to the device and launch the tests through adb shell. I noticed many large inconsistencies in performance, and after lots of debugging, I narrowed it down to memory management. Turns out that calling libc's free() on large blocks takes anything between 10 and 80 milliseconds.

Issue was tested and reproduced on Snapdragon 820 dev board and Samsung Galaxy S7. Both running release build of the OS.

Here is a distilled case that demonstrates the issue.

1. test.cpp

#include <iostream>
#include <chrono>

using namespace std;

// forward declare imported methods
namespace Test
{
void * Alloc( size_t size );
void Free( void * ptr );
void Foo( void * ptr, size_t size );
} // Test namespace

int main()
{
    using hrclock = chrono::high_resolution_clock;
    constexpr size_t kBlockSize = 65 << 20;
    for( int i = 0; i < 100; ++i )
    {
        // allocate
        auto start_time = hrclock::now();
        void * ptr = Test::Alloc( kBlockSize );
        cout << "alloc: " << chrono::duration_cast<chrono::microseconds>( hrclock::now() - start_time ).count() << endl;
        // "process" block
        Test::Foo( ptr, kBlockSize );
        // free
        start_time = hrclock::now();
        Test::Free( ptr );
        cout << "free: " << chrono::duration_cast<chrono::microseconds>( hrclock::now() - start_time ).count() << endl;
    }
    return 0;
}

2. test_lib.cpp

#include <cstdlib>
#include <memory>

namespace Test
{
void * Alloc( std::size_t size ) { return std::malloc( size ); }
void Free( void * ptr ) { std::free( ptr ); }
void Foo( void * ptr, std::size_t size ) { std::memset( ptr, 0, size ); }
} // Test namespace

3. CMakeLists.txt

project( test C CXX )

cmake_minimum_required( VERSION 3.2 )

include_directories( ${CMAKE_CURRENT_SOURCE_DIR} )

add_library( bug_test_lib SHARED test_lib.cpp )
add_executable( bug_test test.cpp )
add_dependencies( bug_test bug_test_lib )
target_link_libraries( bug_test bug_test_lib )

set( CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} -std=c++11" )

4. Build setup

cmake -DCMAKE_BUILD_TYPE=Release \
      -DCMAKE_SYSTEM_NAME=Android \
      -DCMAKE_SYSTEM_VERSION=23 \
      -DCMAKE_ANDROID_STL_TYPE=c++_shared \
      -DCMAKE_ANDROID_ARCH_ABI=arm64-v8a \
      -DCMAKE_ANDROID_NDK_TOOLCHAIN_VERSION=clang \
      -DCMAKE_ANDROID_NDK=/home/david/android-ndk-r14 \

5. Running the test

adb push bug_test /data/local/tmp
adb push libbug_test_lib.so /data/local/tmp
adb shell
cd /data/local/tmp
export LD_LIBRARY_PATH=.
./bug_test

alloc: 87
free: 75567
alloc: 17
free: 75522
alloc: 16
free: 75419
alloc: 15
free: 75915
alloc: 16
free: 75743
alloc: 16
free: 75975
alloc: 17
free: 76090
alloc: 16
free: 75960
alloc: 15
free: 76065
alloc: 16
free: 76004
...

Environment Details

• NDK Version: tested in r14b2 and r13
• Build sytem: cmake 3.7.2
• Host OS: Ubuntu 16.04 x86-64
• Compiler: clang
• ABI: arm64-v8a
• STL: c++_shared
• NDK API level: 23
• Device API level: 23

[DanAlbert]

Thanks for including a benchmark! I'll give this a shot on the devices I have on hand (all Nexus/Pixel things) tomorrow and see if it's the same behavior.

[stephenhines]

If you have the calls to malloc()/free() directly in the same module (or inlined into the module), Clang is probably removing the memory allocation entirely. Compilers are very clever, and malloc()/free() are required to behave a certain way (i.e. you can't rely on running out of memory actually).

[DavidPajak]

You're right. It was the combination of malloc/memset/free that the compiler optimized out completely. If you replace memset with an indirect function call to another compilation unit both variants become consistent. This changes the description of the bug (I will update that soon), but the free() performance issue still remains.

Just guessing: could the internal allocator be trimming the process data segment in the free(), and this, for some reason, takes a lot of time on Android? I did not observe this in any other OS we test (OSX/Linux/Win10).

[DavidPajak]

Small update -- I found Nexus 5 in the office. Recompiled with armeabi-v7a I get numbers similar to Samsung Galaxy S7:

alloc: 49
free: 10650
alloc: 9
free: 10585
alloc: 9
free: 19012
alloc: 10
free: 11555
alloc: 8
free: 11575
alloc: 9
free: 11569
alloc: 9
free: 11572
alloc: 9
free: 11480
alloc: 9
free: 11585

[cferris1000]

What version of the OS did you run this benchmark on? I assume that this is Marshmallow since you are using API level 23. There is a possible issue with frees running on Lollipop or Marshmallow. In order to keep the amount of PSS down, a free can trigger the purge code path in jemalloc, which is expensive. For Nougat, I dialed this back so that the purging doesn't happen quite as often. I don't know if this is the only reason for the free being expensive though.

However, the test is doing a relatively large allocation, and most of native allocators are optimized for much smaller sizes. I'm not familiar with the devices listed, so If they happen to be using the old dlmalloc implementation, I believe it does a munmap for such a large allocation on free.

I ran this on a pixel, but I don't get the same results. In fact, the frees seem to cost less than the allocs. However, I'm using the latest code with the latest version of jemalloc which did update some of the large allocation handling.

I also ran this on a linux machine too, and I see a large cost for frees, about 1000 to 1 for free time to alloc time, which is almost comparable to the results above.

[DavidPajak]

All of the devices I tested so far (Google Nexus 5, Samsung Galaxy S7, and QC SD820 dev board) run Marshmallow (6.0.1).

I did test the code on desktops as our software targets Win/Linux/OSX/Android. For example, my main Ubuntu laptop produces

alloc: 14
free: 609
alloc: 37
free: 603
alloc: 29
free: 352
alloc: 18
free: 549
alloc: 29
free: 473
alloc: 24
free: 219
alloc: 16
free: 465
alloc: 23
free: 549
alloc: 55
free: 293
alloc: 13
free: 367
alloc: 24
free: 676

The difference here is roughly 10:1, not the 1000:1 you report. Similar for OSX/Windows. I expected things to look alike in Android. Having 30-70msec free() calls is rather bothersome :)

Questions:

1. Is there anything I can do now to address this from the NDK point-of-view? For example, some private unsupported call to bionic that will fix the allocator behavior for this kind of workloads. I am only interested in Marshmallow Android since this is the version our device will ship with.
2. Is there anything you guys can fix through NDK release? Backport the fixes from Nougat?
3. What are the exact numbers for Nougat?

[cferris1000]

Unfortunately, there is nothing that can be done on older versions of Android, other than to avoid lots of large allocations and frees.

I verified that on a Nexus 6P running Marshmellow, I see the same issue you see above. Then I put Nougat on the same phone and I see that the alloc and free are much better. For 32 bit code, I see that alloc is ~1800ns and free is ~4500ns. For 64 bit code, I see that alloc is ~1500ns and free is ~2800ns.

On Marshmallow, 32 bit code and 64 bit code are the same: alloc ~5500ns, free ~10,500,000ns.

The only other way to fix this would be to replace the malloc/free calls with a static version of the jemalloc code, but I don't know of an easy way to do that.

[DavidPajak]

I understand. Do you have by a chance the commit to AOS that fixes the issue in Nougat? I could try backporting the patch to M for our internal builds.

[cferris1000]

I do have the CL, but it depends on a new feature that is only in the newer versions of jemalloc (which is why I didn't do this before).

At the same time, you should be able to take the entire jemalloc from Nougat and replace the version in Marshmallow and everything should just work.

[stephenhines]

One other possibility is that if your use case revolves around allocating/freeing large chunks of memory like this, you can create your own pool of allocations. This would allow you to reduce the number of actual malloc()/free() calls that you make, at the expense of keeping the memory alive for longer. It also requires that you provide your own allocation/freeing APIs to the clients of this. It's not always an option, but if you can make it work, you have the option to continue to fine tune the strategy as you need.

[DanAlbert]

(seems there's nothing for us to fix here, so closing)