cancel
Showing results for 
Search instead for 
Did you mean: 

How does nested columns/lists fragment memory?

lzl
New Contributor II

Hi community:

I have a function executed every 5minutes in my application. In the function, I create some nested data structures and update them to a global table with nested columns. Note that each element in the nested column is not a uniform typed list, instead it may be a list of (timestamp; integer).

I found the function will cost more and more time to execute, and running .Q.gc is very slow too. The document of .Q.gc says nested column may cause memory fragment, I am not sure if it is the main reason that slows down the function. 

Also, I did some simple test, and found .Q.gc take significant longer time on nested columns:

q)n:30000000;uids:5000?0Ng;tids:1000?0Ng
q)trades: ([] uid:n?uids;tid:n?tids;sym:n?`1;qty:n?100f; price:n?1000f)
q)\ts select by uid, tid from trades
11557 1610744224
q)\ts .Q.gc[]
134 512
q)\ts select qty, price by uid, tid from trades
21696 1947243520
q)\ts .Q.gc[]
5585 512

Can someone give me more instructions on this issue, especially on the memory allocation and recycle mechanism? Thanks a lot!

1 ACCEPTED SOLUTION

sbruce01
New Contributor III
New Contributor III

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)

sbruce01_0-1686627916290.png

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

sbruce01_1-1686628468640.png

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

View solution in original post

8 REPLIES 8

sbruce01
New Contributor III
New Contributor III

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)

sbruce01_0-1686627916290.png

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

sbruce01_1-1686628468640.png

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
New Contributor III

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).

sbruce01
New Contributor III
New Contributor III

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
New Contributor II

Hi Darren,

Thanks for your reply, I agree with you.  The sample code result shows KDB may be less efficient on processing nested columns (lists of vectors) than on simple columns (vectors)

lzl
New Contributor II

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? 

sbruce01
New Contributor III
New Contributor III

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 @darrenwsun  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:

sbruce01_0-1686639441608.png

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:

sbruce01_3-1686641132667.png

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.

sbruce01_1-1686639809716.png

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.

sbruce01_2-1686640066977.png

 

darrenwsun
New Contributor III

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. 🙂

lzl
New Contributor II

Thanks again, I will try to print the log and check the memory usage. The answer is really helpful😀