KX Community

Find answers, ask questions, and connect with our KX Community around the world.
KX Community Guidelines

Home Forums kdb+ How does nested columns/lists fragment memory?

  • How does nested columns/lists fragment memory?

    Posted by lzl on June 12, 2023 at 12:00 am

    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!

    lzl replied 8 months, 1 week ago 3 Members · 6 Replies
  • 6 Replies
  • Laura

    Administrator
    June 13, 2023 at 12:00 am

    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

    Member
    June 13, 2023 at 12:00 am

    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

    Administrator
    June 13, 2023 at 12:00 am

    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

    Member
    June 13, 2023 at 12:00 am

    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

    Administrator
    June 13, 2023 at 12:00 am

    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

    Member
    June 13, 2023 at 12:00 am

    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.

Log in to reply.