[v5.1] [Heap Trace Standalone] hash map uses doubly linked list, but single linked would be better (IDFGH-9846)

[chipweinberger]

@SoucheSouche

Again, thanks for your work on this PR.

It looks like the hash map entries are storing a doubly linked list. i.e. TAILQ

/* Define struct: linked list of records */
TAILQ_HEAD(heap_trace_record_list_struct_t, heap_trace_record_t); 
typedef struct heap_trace_record_list_struct_t heap_trace_record_list_t;
static heap_trace_hash_list_t hash_map[(size_t)CONFIG_HEAP_TRACE_HASH_MAP_SIZE]; // Buffer used for hashmap entries

AFAICT, a singly linked list is all we need, and would save 50% of the memory.

SLIST_HEAD(heap_trace_record_list_struct_t, heap_trace_record_t*);

Thanks again.

[chipweinberger]

I edited this issue. Hopefully your internal issue tracker supports edits.

[chipweinberger]

Note, the records themselves are doubly linked because:

• during freeing, we traverse backwards
• during printing, we traverse forwards (chronological)

But the hash map does not need this feature.

Also, because the hash map should be large as possible to avoid collisions, we care more that each entry is as small as possible.

[SoucheSouche]

Hi @chipweinberger, thanks for reporting this. It is true that we could use a singly linked list in the hashmap. I will update the feature and get back to you with perf results.

[SoucheSouche]

So it seems that the SLIST has a complexity of O(n) when removing elements from the list. Meanwhile, TAILQ has a complexity of O(1) while removing. To get the same perf with the SLIST has we have with the TAILQ, we have to increase the size of the hashmap in a way that results in taking more memory space than with TAILQ.

[chipweinberger]

STAILQ is more appropriate than SLIST. (my bad)

STAILQ lets you remove from the end in O(1)

SLIST lets you remove from the begining in O(1)

[SoucheSouche]

SLIST_REMOVE and STAILQ_REMOVE are traversing the entire list. Only TAILQ_REMOVE allows for O(1) removal from the list. So I will keep using the doubly linked list.

[chipweinberger]

Ya, thats a good point. Looking at the code, you are right.

Closing this.

[chipweinberger]

We actually could support this.

To use SLIST (saving 50% of the ram!) without hurting perf, we need to replace map_find (which already does a linear traversal), with new methods map_find_and_remove + list_find_and_remove, that way we can traverse the list and remove it at the same time.

This would require a small code change.

       
        if (r_found) {
            if (mode == HEAP_TRACE_ALL) {

                heap_trace_record_t *r_found = list_find(p);

                // add 'freed_by' info to the record
                memcpy(r_found->freed_by, callers, sizeof(void *) * STACK_DEPTH);

            } else { // HEAP_TRACE_LEAKS

                heap_trace_record_t *r_found = list_find_and_remove(p);

                // Leak trace mode, once an allocation is freed
                // we remove it from the list & hashmap
                list_remove(r_found);
            }
        }

[SoucheSouche]

Hi @chipweinberger, I am finally back from my extended leave! I will take a look at that idea as soon as I can :) I'll keep you posted!

[chipweinberger]

Wow nice to hear from you! I was wondering what happened to you =P

Hope you enjoyed your time off!

[SoucheSouche]

yes I did very much! I was on paternity leave :)

[SoucheSouche]

@chipweinberger , I had a look at the code. I am not sure I follow you here. Are you suggesting to make only hash_map a singly linked list?

[chipweinberger]

correct

Note, the records themselves are doubly linked because:

• during freeing, we traverse backwards
• during printing, we traverse forwards (chronological)

But the hash map does not need this feature.

Also, because the hash map should be large as possible to avoid collisions, we care more that each entry is as small as possible.

[SoucheSouche]

I will update hash_map to a singly linked list.

[SoucheSouche]

The update of the hash map was merged internally.

[chipweinberger]

awesome! glad it worked out!

[SoucheSouche]

the update will be available on next github sync. I will close the issue now.