Reduce memory usage

[yzwduck]

Hi, I'm writing a pattern to parse trace v3 files, but my code uses way too much memory (6 GB memory to parse a 10 MB file).

The issue seems to be the unknownData. I tried padding unknownData[expectedEnd - $] but the memory usage is as high as u8. Is there a proper way to mark/skip these bytes without using huge amount of memory? Thanks in advance.

---

Here is my pattern code:

#pragma endian little
#include <std/mem.pat>

struct ChunkPreamble {
    u32 tag;
    u32 subtag;
    u32 size;
    u32 pad;
    u32 expectedEnd = $ + size;

    // parse as much data as possible

    if ($ != expectedEnd) {
        u8 unknownData[expectedEnd - $] [[sealed]];
    }
    std::mem::AlignTo<8>;
};

ChunkPreamble chunks[100] @ 0x00;
// This line might use 6GB memory.
// ChunkPreamble allChunks[while(!std::mem::eof())] @ 0x00;

and here is the test file: test.tracev3.zip

[WerWolv]

Hey
The issue is that ImHex probably has to create thousands of copies of the ChunkPreamble struct when placing the allChunks array into memory.
In your case, there's really not much you can do. If the ChunkPreamble struct had a fixed layout and size, you could mark the type using the [[static]] attribute so only a single instance is being created but that's simply not possible here as you're using an if and an array whose size depends on another member.

[yzwduck]

Hi WerWolv,

Thank you for quick response.

I played with the pattern code to parse first 50, 100, 150, ... ChunkPreamble objects to observe input payload size v.s. memory usage, and the result shows that the memory usage is not linear to input size (which is bad at scaling up)!

Num objects	Input (MB)	Memory (MB)
50	0.77	50
100	1.61	110
150	2.40	211
200	3.17	350
250	3.96	531
300	4.72	750
350	5.41	1000
400	6.14	1260
450	6.85	1580
500	7.55	1930
550	8.28	2320
600	9.06	2740
650	9.91	3210

I wonder if the non-linear (something like O(n^2)) memory usage is an expected behavior?

[paxcut]

Normally when one presents data on the memory use of an algorithm an effort is made to minimize the contributions to the data due to factors unrelated to the algorithm. It takes five minutes to realize that in this case the structure is performing unnecessary calculations. The expected end is calculated to be $ + size so size of the unknown data array is $ + size - $ = size . Similarly the statement if ($ != expectedEnd) is equivalent to if (size != 0).

While it it true that in most environments creating a zero sized array is considered an error, this check is not necessary for pl. You can create zero sized arrays freely, pl just creates nothing but that is exactly what is being asked to do. . I tested the code you posted above using the file you also posted and the average run used 2 Gib.s of ram and took about 20 secs on my aging pc. This is to be expected if the code needed to include those extra calculations and conditional checks. The following code produces the exact same number of real variables (excluding the padding) with the same names at the same positions but in a fraction of the time and using less memory than the input file size itself.

#pragma endian little
#include <std/mem.pat>

struct ChunkPreamble {
    u32 tag;
    u32 subtag;
    u32 size;
    padding[4];
    u8 unknownData[size] [[sealed]];
    padding[-$ & 7]; // -offset & 7 is the number of bytes to next 8 byte aligned address 
};

//u64 fileSize = std::mem::size();
//ChunkPreamble chunks[100] @ 0x00;
// This line might use 6GB memory.
ChunkPreamble allChunks[while(!std::mem::eof())] @ 0x00;

My same aging pc used less than 4 Mib.s of ram and ran for about 1 sec. to produce the same pattern. The relation may still not be linear for non optimized arrays, but that doesn't mean that the code is not fast or efficient. The information comes from then constants that go with the order estimates a c in C*O(n).

[paxcut]

Very interesting observation about the local variable! The pattern is placed 662 times and that's not really high enough to make the pattern consume 3 gigs of ram. When you include the optimization yo the calculation of the alignment padding all 662 instances are placed in 0.024 seconds and don't seem to consume any ram .Adding the local variable makes it take 2 seconds or close to 100 times slower. While I am glad you were able to find a way to avoid using excessive memory I feel that there is something that we are missing that requires further looking into,

[paxcut]

I looked into it and here's what I found. While it is true that including a local variable triggers massive memory use it seems that this is not exactly the case. When you look at how both arrays (with and without local) are created , both report similar sizes of gb size, but the one without the local variable gets optimized right away leaving it in much smaller size. The one with the local variable also gets optimized but not right away. In my computer it takes about half an hour but the gb size is reduced to the same size that the non-local had. I am not sure what's behind this behavior or if it is a bug or not. Somebody with a better understanding of how imhex manages memory will be needed to explain it.

I should clarify that i don't know how long it takes for the array to be optimized. 30 mins is the shortest span I checked and found the memory cleared but it could be a lot less. I waited 5 mins and no change occurred so it is between 5 and 30 minutes in my computer.

[yzwduck]

I also observe that "memory usage*" does drop after idling for 6+ minutes on Windows, with a huge asterisk.

Only "memory (active private working set)" drops, while "memory (private working set)" remains high. ImHex allocates (reserve + commit) about 600 chunks of memory ranging from 1MB to 10MB, most of the area are zero except for the first 65 bytes. Operating system (Windows) might detect these zero bytes (when computer is idle, because it seems to be an expensive operation) and free them from physical memory, reducing "active private working set". ImHex still claims/owns the entire 3+GB memory, as indicated by "private working set".

[paxcut]

I'm not sure what you mean by ImHex claims owning Gb worth of data. I am not looking at the task manager rather confusing memory display. I was only looking at ImHex own memory usage display on the footer and that drops down to mbs after some time. Can you explain the difference between active and not active private working set?

Just to be clear, I am not trying to explain what is going on. When I run both cases under the debugger I can loop over the 662 array element inclusions and each adds some memory to the pattern. In both cases the amount of memory added exceeds the gb mark. Both cases are dynamic arrays and afaik only static arrays can be optimized. How does the array without locals get small memory use? Why does the one with local variables doesn't? Those are open questions and as I commented earlier somebody better acquainted with imhex memory usage needs to answer them so we can determine if there is a bug or not.

[yzwduck]

Apologize for my last reply, every time I mentioned (not active) "private working set", I actually should say "commit size" in TaskMgr or "private bytes" in System Informer instead.

"commit size" is the amount of virtual memory reserved by operation system, while "active private working set" is the physical memory dedicated to the process.

I'll try to compile ImHex and check (play) it with a proper debugger this weekend.

[yzwduck]

I might have found the root issue, but don't know how to fix it because I'm a novice in pattern language.

Let's simplify the pattern, it will parse first 512KB of any test file:

// #pragma debug
struct SimpleChunk {
	u8 dataAxBy[1024] [[sealed]];
	u32 locafe = 0xcafe;
};
SimpleChunk sc[512] @ 0x00;

When processing u32 locafe = 0xcafe, Evaluator::setVariable will be called twice: one from ASTNodeVariableDecl::execute and the other from ASTNodeLValueAssignment::execute. The former allocates too much memory while assigning initial value. Here is the code:

https://github.com/WerWolv/PatternLanguage/blob/bdec1456f6767bd7ea16df8ffd5dd11cb7044467/lib/source/pl/core/ast/ast_node_variable_decl.cpp#L97-L127

This piece of code:

1. create variable (name="locafe", type="u32", offset=0, size=4),
2. create initValue (name="", type="u32", offset=current_read_offset, size=4),
3. assign initValue to variable if available,

When assigning initValue to variable (locafe), the corresponding Evaluator:m_patternLocalStorage is resized to 1024+4 bytes on the first iteration (2048+4 bytes on the second iteration and so on):

https://github.com/WerWolv/PatternLanguage/blob/bdec1456f6767bd7ea16df8ffd5dd11cb7044467/lib/source/pl/core/evaluator.cpp#L647-L648

When assigning 0xcafe to locafe, it only writes 4 bytes to the beginning of storage:

https://github.com/WerWolv/PatternLanguage/blob/bdec1456f6767bd7ea16df8ffd5dd11cb7044467/lib/source/pl/core/ast/ast_node_lvalue_assignment.cpp#L41-L41

https://github.com/WerWolv/PatternLanguage/blob/bdec1456f6767bd7ea16df8ffd5dd11cb7044467/lib/source/pl/core/evaluator.cpp#L589-L594

Running the pattern code with local variable will use (1 + 2 + ... + 512) * 1024B = 131328KB (plus variable itself and some overheaed) more memory than the code without local variable, which is exactly what I have observed (152MB vs 18MB).

I add initValue->setOffset(0) under the branch if (variable->getSection() == ptrn::Pattern::PatternLocalSectionId), and the fix works. But I'm not sure if it breaks something else.

[WerWolv]

Thank you so much for investigating!
That is absolutely an oversight and your proposed fix should be okay. I'll let commit it and let the unit tests run on it to be absolutely sure though.

[yzwduck]

But there is an issue with my proposed fix... It makes me feel uncomfortable until it occurs to me just now that, this line will end up in memcpy with overlapping dest and src, which is undefined behavior in C and C++.

https://github.com/WerWolv/PatternLanguage/blob/7eb8d0f6ef8d8caed167200d677ab3ed7a555254/lib/source/pl/core/evaluator.cpp#L648

[WerWolv]

You're correct yeah. I replaced the problematic calls to memcpy with memmove now to avoid the issue. Thanks again!

[paxcut]

That makes sense and explains the observed behavior that adding a 4 bytes local variable increases the pattern size from mb to gbs as we both reported 4 days ago. I should reran the tests where the two sizes were being reported similar but the case with non local variable was much smaller and see why that was happening.