4 ms·
Why go through all that though? The fundamental principle is that it is flattening the buffer to one linear section of memory, making the pointers jump to a lo
by CyberDildonics 11y ago
Why go through all that though? The fundamental principle is that it is flattening the buffer to one linear section of memory, making the pointers jump to a location that is likely already prefetched and possibly in the same cache line. Dumping to C seems like it is missing the point.
A library like Cereal should be able to do this almost trivially simply by serializing the data, unserializing it to a flat buffer, then pointing to the start of that buffer.
Also I should say that a random forest created by pointer hopping to each new level is a very naive implementation and will take a long time to create due to heap allocation and a long time to traverse due to cache misses.
- ajtulloch 11y agoThat's actually not the case - that's one effect, sure, but when you compared the compiled trees to the flattened trees (the strategy just described), the compiled trees are substantially faster across a range of parameters. See http://tullo.ch/articles/decision-tree-evaluation/ http://tullo.ch/articles/decision-tree-evaluation/ for a detailed evaluation.
- CyberDildonics 11y agoThat's really awesome that you put that together, but I have to think that 200 points and a depth < 2 would basically be a linear search over about 100 elements right? Fundamentally I can't think of any reason compiling a tree would be a good approach in a general sense. Another optimization is to put make splits multiple levels instead of just one. How many might depend on how many you can squeeze into a cache line. If you split position is a float and the dimension is a byte, each split would be 5 bytes. You can squeeze 12 of these into a cache line. You can go 3 level down instead of one by packing 7 of them into a chunk (1 split + 2 splits + 4 splits). This still leaves room for a 32 bit index or pointer for each of the 4 leaves.