Performance/memory considerations for pathfinding lookup tables on RobotC for a small set of paths

Question

I'm writing a C code generator geared toward RobotC and complex tasks for an FTC team, and was wondering about some performance and storage concerns:

1. How much memory is available for my program's data? It'll be mostly pre-defined lookup tables, generally in the form of multidimensional arrays.
2. How much NXT memory is available for my program itself? As in, roughly how much code can I expect to fit into a single RobotC compiled program?
3. How quickly do programs execute, generally? Looking at disassembly most of my generated lines correspond to 2-4 opcodes.

Based on these, I'm trying to make a decision of precomputation vs runtime pathfinding.

I'm using NXT/Tetrix. My major interest at this point with these questions is for pathfinding. I plan to have a 64x64 grid and be running Djisktra's A* algorithm with a heuristic function that assigns a penalty to turns and is as close to consistent as possible (not sure if consistency/monotonicity is doable with the turn penalty).

Roughly 8 paths would be cached if I decide to use the pre-cached lookup tables.

Instead of a set, I'll probably use a boolean array for the set of nodes visited. The fact that I'm working with a square layout will allow me to use a 2D array for the map needed to reconstruct the path.

I'd love some feedback and answers to my question if anyone has any. Thanks!

Answer 1

Just to be clear, my answers assume you are asking about NXT, not the more recent EV3. Also I couldn't find information on how RobotC works on NXT – if it loads native code straight to memory or generates RXE files to run on the NXT VM – so I'll cover both scenarios.

According to the NXT Hardware Developer Kit, the NXT brick's main processor is connected to 64KB RAM. That is the amount of memory available for bare metal programming, that is if you load a native program into the brick, bypassing the original firmware. Of course in this case your program will also have to include drivers to control robot sensors, motors and so on.

If however your program runs on top of the NXT VM, the Executable File Specification says that "[w]hen the VM runs a program, it reads the encoded .RXE file format from flash memory and initializes a 32KB pool of RAM reserved for use by user programs. The .RXE file specifies the layout and default content of this pool. (...) Non-volatile sub-components remain in the file, which the VM can refer to at any time during program execution. The code space is an example of a non-volatile sub-component. The bytecodes never change at run-time, so these bytecodes remain entirely in flash memory."

In other words, RXE programs have a 32KB limit for data structures, but bytecode instructions are not included in this total – they are executed directly from Flash memory, which has a size of 256KB (minus the size of the NXT VM – unfortunately I couldn't find a number for this).

As for processing speed, the NXT HDK says the main processor runs at 48MHz. How this translates to actual speed again depends on whether RobotC programs run natively or on top of the VM. The nxtOSEK project reports their test program achieves a maximum speed of 1,864,000 loop iterations per minute.

But at any rate, I'd bet peripheral pooling, not processing speed, will be you main speed limiting factor. According to Sivan Toledo, "[t]he Interval Timer of the AT91SAM7S256 is used to generate an interrupt every 1 ms. This interrupt is used for time keeping and for running all the periodic tasks of the system." So every 1ms your program stops while the NXT drivers talk to sensors and motors.

So to summarize:

1. RXE programs running on top of the VM are limited to 32KB RAM for data structures, whereas native programs will have 64KB to share between data and code;
2. RXE programs run straight from Flash, so their code size is limited to how much storage is taken by the firmware. For native programs see the previous answer;
3. The brick's main processor runs at 48MHz, but peripheral interruptions occur once every 1ms, so even native code will probably run somewhat slower than that.

I hope this helps.