[Brl.Map] Map or GC: using "C-Maps" leads to stutter

[GWRon]

                    For local count:Int = 1 to 1000
                        Local map:TIntMap = new TIntMap
                        For local pointCount:Int = 0 to 1000
                            map.Insert(pointCount, new TImage)
                        Next
                    Next

using this a multiple times made my game stutter on that users computer from then on. It never "calmed down" .

replacing "TIntMap" with "TMap" and using string(pointCount) as key - and no stutter happens.

TIntMap and the likes (The ones written with C-Code) use:

void bmx_map_intmap_insert( int key, BBObject *value, struct avl_root ** root ) {
	struct intmap_node * node = (struct intmap_node *)GC_malloc_uncollectable(sizeof(struct intmap_node));

GC_malloc_uncollectable defined in blitz.mod/bdwgc/include/gc/gc.h:

/* [...] GC_malloc_uncollectable allocates            */
/* an object that is scanned for pointers to collectible                */
/* objects, but is not itself collectible.  The object is scanned even  */
/* if it does not appear to be reachable.  GC_malloc_uncollectable and  */
/* GC_free called on the resulting object implicitly update             */
/* GC_non_gc_bytes appropriately.               */

Dunno if the GC is bugged there ... and does not get rid of "what to scan" or if the TIntMap (and consortes) implementation does not "free" correctly?

[GWRon]

I replaced

void bmx_map_intmap_insert( int key, BBObject *value, struct avl_root ** root ) {
	struct intmap_node * node = (struct intmap_node *)GC_malloc_uncollectable(sizeof(struct intmap_node));
	node->key = key;
	node->value = value;
	
	struct intmap_node * old_node = (struct intmap_node *)avl_map(&node->link, compare_intmap_nodes, root);

	if (&node->link != &old_node->link) {
		// key already exists. Store the value in this node.
		old_node->value = value;
		// delete the new node, since we don't need it
		GC_FREE(node);
	}
}

with

void bmx_map_intmap_insert( int key, BBObject *value, struct avl_root ** root ) {
	struct intmap_node node;
	node.key = key;
	
	struct intmap_node * found = (struct intmap_node *)TREE_SEARCH(&node, compare_intmap_nodes, root);
	if (found) {
		//nothing to do
	}else{
		//insert new
		struct intmap_node * node = (struct intmap_node *)GC_malloc_uncollectable(sizeof(struct intmap_node));
		node->key = key;
		node->value = value;
		
		avl_add(&node->link, compare_intmap_nodes, root);
	}
}

(maybe one could still use "avl_map" and then replace the pointer with a gc_malloc_... marked one)

A simple benchmark:

SuperStrict
Framework Brl.StandardIO
Import Brl.Map

Local map:TIntMap = New TIntMap

Local o:Object = New TIntMap

Local t:Int = MilliSecs()
For Local i:Int = 0 Until 1000000
	map.insert(i, o)
Next
'now overwrite existing
For Local i:Int = 0 Until 1000000
	map.insert(i, o)
Next
Print "took: " + (MilliSecs() - t)+" ms."

resulted in 260ms for "new" (lookup + add), and 195ms for "old" (avl_map).
Yet it of course also saved 1.000.000 of GC-marked allocations which it needs to cleanup "somewhen".

[GWRon]

Interesting bit: my "new code" segfaults if I have a loop of 10.000.000 instead of 1.000.000:

compare_intmap_nodes (x=0x7fffffffdd20, y=0x480026f281058b08)
    at /home/ronny/Arbeit/Tools/BlitzMaxNG/mod/brl.mod/map.mod/map.c:36
36	        return generic_compare(node_x->key, node_y->key);
(gdb) bt
#0  compare_intmap_nodes (x=0x7fffffffdd20, y=0x480026f281058b08) at /home/ronny/Arbeit/Tools/BlitzMaxNG/mod/brl.mod/map.mod/map.c:36
#1  0x0000000000494f5a in tree_search (entry=entry@entry=0x7fffffffdd20, compare=compare@entry=0x437c40 <compare_intmap_nodes>, root=0x480026f281058b08, 
    root@entry=0x7ffff7e3cfd8) at /home/ronny/Arbeit/Tools/BlitzMaxNG/mod/brl.mod/blitz.mod/tree/tree.c:35
#2  0x0000000000437df3 in bmx_map_intmap_insert (key=4215201, value=0x7ffff7e3cfc0, root=0x7ffff7e3cfd8) at /home/ronny/Arbeit/Tools/BlitzMaxNG/mod/brl.mod/map.mod/map.c:74

[GWRon]

I replaced my code with this:

void bmx_map_intmap_insert( int key, BBObject *value, struct avl_root ** root ) {
	struct avl_root link;
	
	struct intmap_node * old_node = (struct intmap_node *)avl_map(&link, compare_intmap_nodes, root);

	// key already exists. Store the value in this node.
	if (&link != &old_node->link) {
		old_node->value = value;
	// key did not exist. replace node with a managed one
	}else{
		//struct intmap_node * gcmanaged_node = (struct intmap_node *)GC_malloc_explicitly_typed(sizeof(struct intmap_node), maxIntMapDescr);
		struct intmap_node * gcmanaged_node = (struct intmap_node *)GC_malloc_uncollectable(sizeof(struct intmap_node));
		gcmanaged_node->key = key;
		gcmanaged_node->value = value;
		gcmanaged_node->link = link;
	}
}

which reduced the benchmark time to 186ms here. Yet this does not detect "already existing" (how should it - with a "new" Link while the original code just pointed to the first element in the node-struct.)

So I am looking for a way to override a "previously non gc-managed" node with a "now gc managed" one. This would allow to get rid of the unneeded gc-allocs.

PS: I understand that a Map is not intended to be "overwritten" whole the time but as it is not forbidden ... it might be good to increase performance for the "overwriting part" (avoiding nonneeded stuff)

Edit: seems it is not that easy to replace a "stack" allocated node with a "heap" allocated one.

---

My code is not overwriting many map entries (reusing "same key") that often - not often enough to make a difference regarding stuttering. So it most probably is something else (very hard to find out if I cannot replicate it locally)

[GWRon]

Got a handful more reports about that stuttering. So it is less rare than first assumed (especially if you consider how likely you get feedback from users).
All report a "longer game" until it happens - which means more objects in the calculation - and so surely again the 70-80k object creation+deletion amount.

@woollybah Were you somehow able to replicate such an issue or should I try to create a complete "sample app" ? I assume it only stutters if you create a lot of objects for the c-maps, then delete it AND then are "normally" using the GC (so doing your normal app logic stuff).
A simple test application just utilizing the map and a basic "while"-loop with a "frame time chart" probably won't show the stutter.
Maybe even Multithreading has an impact here (if the map is created/used/filled from a thread - dunno how nice the GC plays with threads at all)