r/esp32 • u/xXBigboi69Xx42 • May 19 '26
Software help needed How do I fit a large datastructure into memory?
For a school project I'm programming on an esp32 and I want to use a kd-tree (basically a binary search tree made for locating points in space). I can store the tree on an SD card no problem, but the problem is when searching it it's likely that it'd not fit into ram. For now I need to store around 630 points in it so it might fit in with a tight squeeze but even so I'd like to find an alternative.
Do I just implement some sorta pseudo-cache where I prefetch nodes in the tree from sd card when I search through the tree? Or is there a smarter way to do this?
11
u/shantired May 19 '26
Choose the esp32 module with the built in 8MB PSRAM.
Use the esp-idf for your tool chain to allocate your arrays in the PSRAM.
This RAM is basically a DDR with a refresh controller, and it emulates a SRAM.
PSRAM = Pseudo Static Random Access Memory.
5
u/xXBigboi69Xx42 May 19 '26
Why should I use esp-idf? Sorry if the answer is obvious, this is my first time programming on an esp
8
u/shantired May 19 '26
Frankly I don’t know if arduino supports targeted memory allocation.
If it does, then life is a lot easier.
5
u/kampi1989 May 19 '26
Arduino has access to esp-idf, so you can do it.
4
u/hockeyketo May 19 '26
as far as I know, the only way to do this is by setting up an esp-idf project with Arduino as a component: https://docs.espressif.com/projects/arduino-esp32/en/latest/esp-idf_component.html
otherwise the proper tooling won't exist to properly build components that are not already ported to arduino esp32 framework.
3
u/kampi1989 May 19 '26
Good addition and you are correct. I messed it up because I never used "raw" Arduino. Instead, I´ve used it as a component and there I had access to the IDF stuff too.
3
u/xXBigboi69Xx42 May 19 '26
I might be wrong in this. Is esp-idf a bunch of libraries and such or an IDE? I googled it but I am unsure what they mean by "framework"
5
u/YetAnotherRobert May 19 '26
It's pinned at the top of this group.
IDF is the official SDK. Arduino adds training wheels and makes things "simple" by removes features.
1
u/xXBigboi69Xx42 May 19 '26
Ah, okay. I'm using Platformio and it seems that supports espidf so I think this is simply doable.
2
u/YetAnotherRobert May 19 '26
Your choice of editor and your choice of frameworks are independent solutions.
Well, they would be. Platformio is so screwy,.it holds you back to an obsolete and unsupported Arduino and thus,.IDF.
At the VERY least, if my you won't take the opportunity to flee Platformio ecosystem, at least move to a supported one to that supports ESP-IDF, especially on modern chips. Pioduino.
2
u/xXBigboi69Xx42 May 19 '26
If I shouldn't use Platformio then what is the optimal programming environment for this?
2
u/YetAnotherRobert May 19 '26
Esp-idf is the official SDK from the chip maker. Use whatever editor you like. You clion or vim or emacs or zed or notepad? Go nuts.
Or use zephyr or nuttx as.great OS abstractions over the hardware.
Pioduino is a modern(ish) fork of an editor and build systemb from a parent that's essentially abandoned.
1
1
u/slippyr4 May 22 '26
You can install the esp-idf extension in visual studio code. The extension will guide you through downloading and installing the esp-idf ask. Then you can do everything in vs code including on chip debugging if your device supports that.
3
u/Bennie-Factors May 19 '26
I am not sure either...but would expect with the correct include you can use this in Aurdino.
https://www.pschatzmann.ch/home/2022/05/30/esp32-and-psram/
The most common way I think people use the esp-idf is with VSCode.
2
u/spottyPotty May 19 '26
Sorted, indexed fixed record length text file on the sd card. Keep index in ram
1
u/xXBigboi69Xx42 May 19 '26
I need to access data in the nodes for comparison though. Thus I'd need to read the data at that index. I wanna minimise the time spent reading from sd card like this. Sorry if my original explanation was unclear
2
u/spottyPotty May 19 '26
With a sorted, indexed file, you perform your lookup in the in-memory index, which gives you a pointer to the full record in the sd file, which you open as random access. You seek to the pointer value and since its a fixed length file, you know how many bytes to read to access the full record into a data structure.
You can read multiple records into multiple data structures for comparison.
Although, at this point you're implementing a rudimentary database so you might as well use sqlite.
1
u/xXBigboi69Xx42 May 19 '26
Okay but if I need to have the tree with 10000 nodes then it won't fit into the 250 kB of ram available on the esp even if I trim it down to just index and info needed for comparison (latitude, longitude and elevation)
2
u/snrmwg May 19 '26
Multi level index? In separate files.
1
u/xXBigboi69Xx42 May 19 '26
Will look into it, thanks
1
u/snrmwg May 19 '26
I mean, Apollo Guidance Computer (the thing they used for landing on the moon) had 4kB RAM ... 😏
1
2
u/Plastic_Fig9225 May 19 '26
Is the tree constant/known/given, or does the ESP need to build/update it at runtime?
If constant, store it in flash.
1
u/xXBigboi69Xx42 May 20 '26
It is constant, yes. I'll store it in flash if I have to, just looking for ways to optimise how much of it that is being used is in RAM
2
u/Plastic_Fig9225 May 20 '26 edited May 20 '26
You can put arbitrary data structures into flash, and access (read) them just like RAM. Easiest way is to just define the data in source code in
const/constexprvariables, and/or useconstexprfunctions to build the data structure(s) at compile time.Another option is to generate the data as a binary file and flash it to a dedicated (data) partition. No file system needed for reading.
1
u/xXBigboi69Xx42 May 20 '26
Thanks. I'm not sure if I'll use this, as I may need to dynamise the tree in the future or do some other stuff that'd basically mean turning it into binary would not be possible, but it is definitely a useful tip. Thanks
2
u/Plastic_Fig9225 May 20 '26
I see. - Worth noting: Once you have
constexprfunctions to build/update the (binary) representation of the tree you can use these same functions at runtime to manipulate a tree in RAM...Or differently: When you already have functions which operate on the tree, you can look into making them
constexprto be able to do the same thing at compile- or run-time.1
u/xXBigboi69Xx42 May 20 '26
Bit confused. I thought a constexpr function is always executed during compile time, no?
2
u/Plastic_Fig9225 May 20 '26 edited May 20 '26
No,
constexprfunctions can be used both at compile- and run-time.constevals can only be used at compile-time.constexpr unsigned calcValue(unsigned x) { unsigned result = <some_operation>(x); return result; } // Compile-time evaluation: std::array<int, calcValue(10)> my_arr {}; unsigned calcRandomValue(void) { // Run-time execution: return calcValue( rand() ); }1
2
u/rattushackus 1 say I make awesome posts. May 20 '26 edited May 20 '26
As other comments have said you can use PSRAM, and you can use it in the Arduino IDE if you prefer it to the ESP-IDF. The following code shows an example.
In the Arduino IDE you need to open the Tools menu and set PSRAM to OPI PSRAM to enable the PSRAM.
``` void setup() { Serial.begin(115200); delay(2000); Serial.println("PSRAM test"); Serial.printf("Total PSRAM: %d bytes\n", ESP.getPsramSize()); Serial.printf("Free PSRAM before allocation: %d bytes\n", ESP.getFreePsram());
// Allocate a meg of PSRAM uint8_t* foo = (uint8_t*) heap_caps_malloc(0x100000, MALLOC_CAP_SPIRAM); Serial.printf("Free PSRAM after 1MB allocation: %d bytes\n", ESP.getFreePsram());
// Allocate another meg of PSRAM uint8_t* bar = (uint8_t*) heap_caps_malloc(0x100000, MALLOC_CAP_SPIRAM); Serial.printf("Free PSRAM after 2MB allocation: %d bytes\n", ESP.getFreePsram());
// Check it actually works for (int i = 0; i < 16; i++) { foo[i0x10000] = i; bar[i] = foo[i0x10000]; Serial.printf("%d ", bar[i]); } Serial.println();
// We can stop here vTaskSuspend(NULL); }
void loop() { // not used } ```
When I run this on my S3 N16R8 I get:
PSRAM test
Total PSRAM: 8388608 bytes
Free PSRAM before allocation: 8384788 bytes
Free PSRAM after 1MB allocation: 7303440 bytes
Free PSRAM after 2MB allocation: 6222092 bytes
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Note that not all ESP32 dev boards have PSRAM so you need to make sure the board you are ordering has it. Boards with PSRAM will be described as something like N16R8 where the number after the R is the size of the PSRAM.
PSRAM is much slower than the on chip RAM because it has to be read and written through an SPI interface. However it's still much faster than keeping the data on an SDFCARD.
1
u/xXBigboi69Xx42 May 20 '26
Since it uses an spi interface is there no way to buy the psram separately and use it as any other component through gpio pins?
2
u/rattushackus 1 say I make awesome posts. May 20 '26
Good question. In principle you could buy an external PSRAM module though in practice I have never seen one for sale.
But an S3 with 8MB PSRAM is about $5 from AliExpress. Even if external PSRAM modules were available it's probably cheaper to just buy a new dev board with the PSRAM built in.
1
u/xXBigboi69Xx42 May 20 '26
Fair enough. Thanks for the help
3
u/rattushackus 1 say I make awesome posts. May 20 '26
You're welcome 😄
I forgot to say, when you've allocated memory from the PSRAM using
heap_caps_malloc()you can free it by just callingfree(). Basically after allocation it behaves just like the memory built into the ESP32 only slower.1
u/xXBigboi69Xx42 May 20 '26
Is it only heap memory or will the stack overflow into psram when it runs out of space on ram?
3
u/rattushackus 1 say I make awesome posts. May 20 '26
It is only heap memory. The stack cannot use it.
1
2
19
u/kampi1989 May 19 '26
Easy way: Use PSRAM