BitMap class consumes double expected memory

[belzecue]

Godot version:
3.3 stable

OS/device including version:
Linux Ubuntu 20.04.2

Issue description:
Stable documentation explains the BitMap class as:

A two-dimensional array of boolean values, can be used to efficiently store a binary matrix (every matrix element takes only one bit) and query the values using natural cartesian coordinates.

"Every matrix element takes only one bit."

In Godot 3.3, I created a BitMap of size 1024 x 262,144 and printed the memory stats immediately before and after object creation. It showed the BitMap consuming double the memory I expected. The BitMap is 268,435,456 bits = 33,554,432 bytes, i.e. 33.5 MB.

Before creation (MB) - Dynamic: 0.000272; Static: 32.828644
After creation (MB) - Dynamic: 0.000272; Static: 99.940192

So that's 67 MB memory consumed for that one BitMap, which is double what you'd expect if the BitMap is using bits/bytes. It's like BitMaps actually work with Uint16 instead of bytes, and ignore the extra 8 bits per word. That would explain why double the memory is being allotted. But looking at resources/bit_map.h and resources/bit_map.cpp, everything is uint8_t, so I must be missing something here.

Steps to reproduce:
Using the simple code below, memory stats show that creating one BitMap sized to 1024 x 262144 bits, i.e. 33,554,432 bytes, actually consumes 67,109,160 bytes, which is very close to 2 x 33,554,432 (67,108,864).

Minimal reproduction project:

func _ready():
	print("Pre-assign: %s" % Performance.get_monitor(Performance.MEMORY_STATIC))
	var _bm: BitMap = BitMap.new()
	print("BitMap.new() but not created: %s" % Performance.get_monitor(Performance.MEMORY_STATIC))
	_bm.create(Vector2(1024, 262144))
	print("BitMap created: %s" % Performance.get_monitor(Performance.MEMORY_STATIC))
	_bm = null
	print("BitMap nulled: %s" % Performance.get_monitor(Performance.MEMORY_STATIC))

[kleonc]

It happens because CowData used by Vector which is used internally by the BitMask allocates memory amount being a power of 2 and in this line:

godot/scene/resources/bit_map.cpp

Line 41 in ee44982

bitmask.resize(((width * height) / 8) + 1);

there's this + 1 which in this case results in resizing to (1024 * 262144) / 8 + 1 = 2²⁵ + 1 bytes and thus size being allocated is 2²⁶ bytes. The issue here with the BitMask itself is that it requests more bytes than it needs when its size is a multiply of 8.

[belzecue]

Thank you for investigating, kleonc. I just want to double check I understand the explanation because, having tested more, I see I can use a Po8 size and get correct memory allocation e.g. in the test case, if I reduce x dimension by 1:

_bm.create(Vector2(1023, 262144))

1023 x 262144 = 268,173,312 bits/size
268,173,312 % 8 = 0, so it's Po8, same as test case.

Expected allocation is around 33.5 MB, and that is what happens, which I was not expecting based on my understanding of this issue:

Pre-assign: 32621520
BitMap.new() but not created: 32622224
BitMap created: 66176952
BitMap nulled: 32622176

[kleonc]

I could've probably explain it better. So I'd point out two different aspects here:

---

1. How many bytes does BitMap say it needs? As mentioned before currently it's calling bitmask.resize(((width * height) / 8) + 1); which means that for width * height being a multiply of 8 it requests a 1 byte more than it actually needs to store all of its bits:

width * height (bits needed)	ceil((width * height) / 8.0) (whole bytes needed)	((width * height) / 8) + 1 (bytes requested)
8k + 0	k	k + 1
8k + 1	k + 1	k + 1
8k + 2	k + 1	k + 1
8k + 3	k + 1	k + 1
8k + 4	k + 1	k + 1
8k + 5	k + 1	k + 1
8k + 6	k + 1	k + 1
8k + 7	k + 1	k + 1

So currently when BitMap's size in bits is a multiple of 8 it requests a 1 byte more than it actually needs and I'd say it's a bug.

---

2. How many bytes are being allocated when BitMap requests k bytes? As mentioned before currently it depends on the Vector / CowData which would allocate the smallest power of 2 bytes which is not less than k:

bytes requested	bytes allocated
2m + 0	2m
2m + 1	2m + 1
...	...
2m + 1 + 0	2m + 1
2m + 1 + 1	2m + 2

In general for k > 0 bytes requested there will be 2^{ceil(log₂(k))} bytes allocated.

---

In #48549 I've addressed the first issue so the BitMap won't request more bytes than it actually needs to store all of the bits.

To address the "unexpected amount of memory allocated" part of your issue what would need to be changed is either how Vector / CowData allocates the memory or what BitMask uses internally as a storage.

[belzecue]

I built an executable from 3.3-stable plus your one-line fix (3.3...belzecue:3.3-stable-AF), and memory now behaves as expected.

3.3-stable:

BitMap size = (1, 1) bits / 0.125 bytes; allocated: 0 bytes; ratio: 0.00
BitMap size = (1, 2) bits / 0.25 bytes; allocated: 0 bytes; ratio: 0.00
BitMap size = (1, 4) bits / 0.5 bytes; allocated: 0 bytes; ratio: 0.00
BitMap size = (1, 8) bits / 1 bytes; allocated: 4 bytes; ratio: 4.00
BitMap size = (1, 16) bits / 2 bytes; allocated: 4 bytes; ratio: 2.00
BitMap size = (1, 32) bits / 4 bytes; allocated: 8 bytes; ratio: 2.00
BitMap size = (1, 64) bits / 8 bytes; allocated: 16 bytes; ratio: 2.00
BitMap size = (1, 128) bits / 16 bytes; allocated: 32 bytes; ratio: 2.00
BitMap size = (1, 256) bits / 32 bytes; allocated: 64 bytes; ratio: 2.00
BitMap size = (1, 512) bits / 64 bytes; allocated: 128 bytes; ratio: 2.00
BitMap size = (1, 1024) bits / 128 bytes; allocated: 256 bytes; ratio: 2.00
BitMap size = (1, 2048) bits / 256 bytes; allocated: 512 bytes; ratio: 2.00
BitMap size = (1, 4096) bits / 512 bytes; allocated: 1024 bytes; ratio: 2.00
BitMap size = (1, 8192) bits / 1024 bytes; allocated: 2048 bytes; ratio: 2.00
BitMap size = (1, 16384) bits / 2048 bytes; allocated: 4096 bytes; ratio: 2.00
BitMap size = (1, 32768) bits / 4096 bytes; allocated: 8192 bytes; ratio: 2.00
BitMap size = (1, 65536) bits / 8192 bytes; allocated: 16384 bytes; ratio: 2.00
BitMap size = (1, 131072) bits / 16384 bytes; allocated: 32768 bytes; ratio: 2.00
BitMap size = (1, 262144) bits / 32768 bytes; allocated: 65536 bytes; ratio: 2.00
BitMap size = (1, 524288) bits / 65536 bytes; allocated: 131072 bytes; ratio: 2.00
BitMap size = (1, 1048576) bits / 131072 bytes; allocated: 262144 bytes; ratio: 2.00
BitMap size = (1, 2097152) bits / 262144 bytes; allocated: 524288 bytes; ratio: 2.00
BitMap size = (1, 4194304) bits / 524288 bytes; allocated: 1048576 bytes; ratio: 2.00
BitMap size = (1, 8388608) bits / 1048576 bytes; allocated: 2097152 bytes; ratio: 2.00
BitMap size = (1, 16777216) bits / 2097152 bytes; allocated: 4194304 bytes; ratio: 2.00
BitMap size = (1, 33554432) bits / 4194304 bytes; allocated: 8388608 bytes; ratio: 2.00
BitMap size = (1, 67108864) bits / 8388608 bytes; allocated: 16777216 bytes; ratio: 2.00
BitMap size = (1, 134217728) bits / 16777216 bytes; allocated: 33554428 bytes; ratio: 2.00
BitMap size = (1, 268435456) bits / 33554432 bytes; allocated: 67108860 bytes; ratio: 2.00
BitMap size = (1, 536870912) bits / 67108864 bytes; allocated: 134217724 bytes; ratio: 2.00
BitMap size = (1, 1073741824) bits / 134217728 bytes; allocated: 268440060 bytes; ratio: 2.00
BitMap size = (1, -2147483648) bits / -268435456 bytes; allocated: 688 bytes; ratio: -0.00

3.3-stable + your fix:

BitMap size = (1, 1) bits / 0.125 bytes; allocated: 0 bytes; ratio: 0.00
BitMap size = (1, 2) bits / 0.25 bytes; allocated: 0 bytes; ratio: 0.00
BitMap size = (1, 4) bits / 0.5 bytes; allocated: 0 bytes; ratio: 0.00
BitMap size = (1, 8) bits / 1 bytes; allocated: 0 bytes; ratio: 0.00
BitMap size = (1, 16) bits / 2 bytes; allocated: 4 bytes; ratio: 2.00
BitMap size = (1, 32) bits / 4 bytes; allocated: 4 bytes; ratio: 1.00
BitMap size = (1, 64) bits / 8 bytes; allocated: 8 bytes; ratio: 1.00
BitMap size = (1, 128) bits / 16 bytes; allocated: 16 bytes; ratio: 1.00
BitMap size = (1, 256) bits / 32 bytes; allocated: 32 bytes; ratio: 1.00
BitMap size = (1, 512) bits / 64 bytes; allocated: 64 bytes; ratio: 1.00
BitMap size = (1, 1024) bits / 128 bytes; allocated: 128 bytes; ratio: 1.00
BitMap size = (1, 2048) bits / 256 bytes; allocated: 256 bytes; ratio: 1.00
BitMap size = (1, 4096) bits / 512 bytes; allocated: 512 bytes; ratio: 1.00
BitMap size = (1, 8192) bits / 1024 bytes; allocated: 1024 bytes; ratio: 1.00
BitMap size = (1, 16384) bits / 2048 bytes; allocated: 2048 bytes; ratio: 1.00
BitMap size = (1, 32768) bits / 4096 bytes; allocated: 4096 bytes; ratio: 1.00
BitMap size = (1, 65536) bits / 8192 bytes; allocated: 8192 bytes; ratio: 1.00
BitMap size = (1, 131072) bits / 16384 bytes; allocated: 16384 bytes; ratio: 1.00
BitMap size = (1, 262144) bits / 32768 bytes; allocated: 32768 bytes; ratio: 1.00
BitMap size = (1, 524288) bits / 65536 bytes; allocated: 65536 bytes; ratio: 1.00
BitMap size = (1, 1048576) bits / 131072 bytes; allocated: 131072 bytes; ratio: 1.00
BitMap size = (1, 2097152) bits / 262144 bytes; allocated: 262144 bytes; ratio: 1.00
BitMap size = (1, 4194304) bits / 524288 bytes; allocated: 524288 bytes; ratio: 1.00
BitMap size = (1, 8388608) bits / 1048576 bytes; allocated: 1048576 bytes; ratio: 1.00
BitMap size = (1, 16777216) bits / 2097152 bytes; allocated: 2097152 bytes; ratio: 1.00
BitMap size = (1, 33554432) bits / 4194304 bytes; allocated: 4194304 bytes; ratio: 1.00
BitMap size = (1, 67108864) bits / 8388608 bytes; allocated: 8388608 bytes; ratio: 1.00
BitMap size = (1, 134217728) bits / 16777216 bytes; allocated: 16777216 bytes; ratio: 1.00
BitMap size = (1, 268435456) bits / 33554432 bytes; allocated: 33554436 bytes; ratio: 1.00
BitMap size = (1, 536870912) bits / 67108864 bytes; allocated: 67108868 bytes; ratio: 1.00
BitMap size = (1, 1073741824) bits / 134217728 bytes; allocated: 134217732 bytes; ratio: 1.00
BitMap size = (1, -2147483648) bits / -268435456 bytes; allocated: 268435444 bytes; ratio: -1.00

func test1():
	var x: int = 1
	var tree: SceneTree = get_tree()
	for y in range(0, 32):
		var start_mem: int = Performance.get_monitor(Performance.MEMORY_STATIC)
		var _bm: BitMap = BitMap.new()
		_bm.create(Vector2(x, 1 << y))
		var end_mem: int = Performance.get_monitor(Performance.MEMORY_STATIC) - start_mem - 512
		var size: Vector2 = _bm.get_size()
		var bits: int = size.x * size.y
		var bytes: float = bits / 8.0
		print("BitMap size = %s bits / %s bytes; allocated: %s bytes; ratio: %.2f" % [size, bytes, end_mem, (end_mem / bytes)])
		_bm = null
		yield(tree.create_timer(0.05),"timeout")

[kleonc]

I built an executable from 3.3-stable plus your one-line fix (3.3...belzecue:3.3-stable-AF), and memory now behaves as expected.

... for BitMap size in bytes being a Po2 (that what was fixed in there). If you'd repeat your test with creating BitMaps like this:

		_bm.create(Vector2(x, (1 << y) + 1))

there will still be (almost) 2.0 actual size / allocated memory ratio.

[belzecue]

Darn it, I got mixed up. Yes, 2x allocation for non Po2. I suppose I'll be sticking to Po2 size assignment in the meanwhile. Thanks again for providing this useful workaround.

[akien-mga]

This was only partially fixed by #48549, what's left to fix is maybe to add a note in the documentation that BitMap memory usage grows in powers of two?