How does nested columns/lists fragment memory?

[Laura]

Hi there,

Firstly, what you’re seeing here isn’t memory fragmentation due to nested columns. Looking at the documentation the memory fragmentation issue in relation to garbage collection is when KDB/Q  can’t find contiguous blocks of memory to release back to the OS due to the memory being fragmented. Noting specifically here that although the used memory is low, even after garbage collection the heap remains large (see attached snippet). The solution of this fragmentation is to serialise your data, release then de-serialise (see the comments within the coded example)

 

Secondly, the coded example you provided doesn’t contain nested columns. An example of a nested column, continuing from your definition of trades:

select nested from update nested:n#enlist (.z.p;3i) from trades

Where the column type of nested is a mixed list with datatypes of 2-tuples at every index of the nested array

 

In relation to the time taken to garbage collect, you’ll find your second query requires more memory allocated to the process to complete, thus more time to release the memory.

To solve the issue of time for you, I’d advise using Immediate Garbage Collection  which can be started within the Q session using the commandline argument of -g 1 or dynamically on the process using g 1. This will mean you don’t have to manually invoke .Q.gc[] as the system will automatically release memory blocks back to the OS upon availability.

More reading on Memory Fragmentation for interest here

Regards,

Sam B

[darrenwsun]

Note that the second query generates a table with compound/nested columns qty and price.

I don’t know why the second .Q.gc call takes significantly longer, given that the memory usage of the two queries are comparable (although the second takes slightly more). But I don’t think it’s relevant to fragmented memory; after all, the space of whole temporary result is released rather than part of it, as is the case from the .Q.gc doc. My suspect is that it just takes longer to garbage collection when it involves nested columns (aka lists of vectors) than simple columns (aka vectors).

[Laura]

Ah yes you’re right, multiple entries of qty/price for a given uid/tid will create nested columns in the by clause response.

Agreed, memory fragmentation definitely not the issue here, just providing documentation supporting that claim

[lzl]

Hi Sam,

Thanks for your detailed explanation and documents. I have tried the Immediate garbage collection mode in my application but didn’t get much speed up. I create nested list (mixed with different datatypes) and may release part of it in my function.  And I have some further questions:

1. Will creating temporary nested list within a function and update them locally (without updating to global variables) cause memory fragmentation? For example: I first create a nested list nl and then reassign nl:nl[:: ; 0]
2. If I reassign  nl: nl[:: ; 0] and also update nl to a global variable `.test.nl insert nl, will it cause memory fragmentation?
3. In which scenario will variable declaration operation (:) cause memory allocation in KDB?

[Laura]

---

I have tried the Immediate garbage collection mode in my application but didn’t get much speed up.

---

Can I clarify what metric you’re using when you say you didn’t get much speed up. Just to restate, when you use immediate garbage collection you no longer need to call .Q.gc[] in your script, so most of the slowness of your script will come from the aggregations themselves. You can compare the two methods by logging out .Q.w[] and .z.p at different intervals of your script.

Regarding the memory fragmentation it’s not something you need to consider at this point, as mentioned by   the space of the whole temporary result is released rather than part of it.

1. Yes, deallocating part of a nested structure will mean that part cannot be released if the other part is referenced, as per the comments in the docs:

 

2. Yes for the same reason as 1 if you haven’t deleted nl from the local namespace. The global table will also reference the same memory locations as nl so even if nl is deleted from the local namespace you will have this problem:

 

I’d advise experimenting with the code provided in the docs as I have here, you might find some of the answers to your questions by observing how much memory is released back to the OS when using globals/nested variables.

3. I believe it’s when new data is referenced. E.g.

 

Note when assigning b:a there is no memory increase, but once a is modified it needs to create a new memory allocation and b still uses the same memory space as a previously occupied.

 

But to reiterate, the problem of speed should be solved with immediate garbage collection (if you could verify with logs), and the issue of memory fragmentation shouldn’t be particularly relevant to you at this point. However if it does become an issue, you’ll see that reflected in .Q.w[] with the used being orders of magnitude lower than the heap even after manual .Q.gc[]. The solution is to serialise, release and de-serialise the variable that’s referencing the fragmented memory (your global table) periodically, or pursue a solution that doesn’t include nested vectors.

 

 

[darrenwsun]

For 2, precisely it depends. If we tweak the example to let the first element to be an integer (or any other value of atomic type), we will see some effective garbage collection.

q)v:{(10;10000#"b")} each til 100000 
q).Q.w[] 
used| 1643008048 
heap| 1677721600 
peak| 1677721600 
wmax| 0 mmap| 0 
mphy| 7978725376 
syms| 665 
symw| 28405 

q).glob.t:([]a:`long$()) 
q)`.glob.t upsert flip enlist[`a]!enlist v[;0] 
`.glob.t 

q).Q.gc[] 
1543503872 

q).Q.w[] 
used| 1406896 
heap| 134217728 
peak| 1677721600 
wmax| 0 
mmap| 0 
mphy| 7978725376 
syms| 668 
symw| 28496

My explanation towards the different behaviors is that in the above example, since v[;0] is an int vector, its elements have to be in consecutive memory and thus it is a value copy from the original list. As such deleting v allows recycling the memory taken by v. While with the earlier example, v[;0] is a list of “references” to the elements in the original list v, so deleting v doesn’t remove all references to the memory blocks used by v (the references are now in .glob.t).

 

For 3, the shorter answer is that kdb uses copy-on-write.