It’s stupid. It’s ugly. Its also measurable performance gain.
Let’s write a node-based interpreter, just like the one we have, only smaller:
#include <vector>
struct Node {
virtual void eval() = 0;
};
void eval ( std::vector<Node *> & nodes ) {
for ( auto n : nodes ) {
n->eval();
}
}
Disassembler (CLANG 15 -O3) says its good:
mov rbx, qword ptr [rdi] // this is nodes.begin()
mov r14, qword ptr [rdi + 8] // this is nodes.end()
cmp rbx, r14 // if they are the same, we skip the loop
je .LBB0_3
.LBB0_1:
mov rdi, qword ptr [rbx] // vtable_ptr = nodes_ptr
mov rax, qword ptr [rdi] // call_ptr = vtable_ptr[0]
call qword ptr [rax] // this is n->eval() i.e. (*call_ptr)()
add rbx, 8 // nodes_ptr ++
cmp rbx, r14 // if nodes_ptr!=nodes.end() we continue looping
jne .LBB0_1
Sometimes we need an index of a node. Easy-peasy:
void eval ( std::vector<Node *> & nodes ) {
for ( int i=0; i!=nodes.size(); ++i ) {
nodes[i]->eval(); // and we can use index i
}
}
But now disassembler hates us:
mov rax, qword ptr [rdi] // this is nodes.begin()
cmp qword ptr [rdi + 8], rax // if its the same as nodes.end() we skip the loop
je .LBB0_3
mov r14, rdi
xor ebx, ebx
.LBB0_2:
mov rdi, qword ptr [rax + 8*rbx] // vtable_ptr = nodes.data() [i]
mov rax, qword ptr [rdi] // call_ptr = vtable_ptr[0]
call qword ptr [rax] // this is n->eval() is (*call_ptr)()
inc rbx // this is our index = i++
mov rax, qword ptr [r14] // this is b = nodes.begin()
mov rcx, qword ptr [r14 + 8] // this is e = nodes.end()
sub rcx, rax // this is .size() = (e - b) / 8
sar rcx, 3
cmp rbx, rcx // if i!=.size() we keep looping
jne .LBB0_2
What happens? In one word - aliasing. n->eval() can technically resize nodes.
So it reads an computes .size() every single iteration.
I know, I know, its nothing new. There are tones of articles about it.
And yet like a mad man I keep writing that code like an incantation every single time I need an index.
But no more:
void eval3 ( std::vector<Node *> & nodes ) {
for ( int i=0, is=nodes.size(); i!=is; ++i ) {
nodes[i]->eval(); // and we can use index i
}
}
This is better:
mov rax, qword ptr [rdi + 8] // this is nodes.begin()
sub rax, qword ptr [rdi] // this is nodes.end()
shr rax, 3 // this is .size()
test eax, eax // if its zero, we skip the loop
je .LBB0_3
mov r14, rdi
mov r15d, eax
xor ebx, ebx
.LBB0_2:
mov rax, qword ptr [r14] // we load nodes.data() here
mov rdi, qword ptr [rax + 8*rbx] // vtable_ptr = nodes.data() [i]
mov rax, qword ptr [rdi] // call_ptr = vtable_ptr[0]
call qword ptr [rax] // this is n->eval() is (*call_ptr)()
inc rbx // this is our index=i++
cmp r15, rbx // if i!=size() we keep looping
jne .LBB0_2
Now this is getting to the impractical territory. We now need to cache two variables, write more incantations:
void eval4 ( std::vector<Node *> & nodes ) {
auto data = nodes.data(); for ( int i=0, is=nodes.size(); i!=is; ++i ) {
data[i]->eval(); // and we can use index i
}
}
However all is well in the land of disassembly:
mov r14, qword ptr [rdi] // this is b = nodes.begin()
mov rax, qword ptr [rdi + 8] // this is e = nodes.end()
sub rax, r14 // this is nodes.size() = (e-b) / 8
shr rax, 3
test eax, eax // if its 0 we skip the loop
je .LBB0_3
mov r15d, eax
xor ebx, ebx
.LBB0_2:
mov rdi, qword ptr [r14 + 8*rbx] // vtable_ptr = nodes_data [index]
mov rax, qword ptr [rdi] // call_ptr = vtable_ptr[0]
call qword ptr [rax] // this is n->eval() is (*call_ptr)()
inc rbx // this is index = i++
cmp r15, rbx // if index!=.size() we keep looping
jne .LBB0_2
The prologue of the loop is longer, but at least the loop itself is good.
Let’s add an index, and actually pass it to the node like this:
struct Node {
virtual void eval(int i) = 0;
};
void eval ( std::vector<Node *> & nodes ) {
int i=0;
for ( auto n : nodes ) {
n->eval(i);
i ++;
}
}
And look, all is well in the land of disassembly:
mov rbx, qword ptr [rdi] // nodes_ptr = nodes.begin
mov r14, qword ptr [rdi + 8] // nodes.end
cmp rbx, r14 // if they are the same, skip the loop
je .LBB0_3
xor ebp, ebp // index = 0
.LBB0_2:
mov rdi, qword ptr [rbx] // vtable = nodes_ptr
mov rax, qword ptr [rdi] // call_ptr = vtable_ptr[0]
mov esi, ebp // pass i as first argument
call qword ptr [rax] // (*call_ptr) ( i )
inc ebp // i ++
add rbx, 8 // nodes_ptr ++
cmp rbx, r14 // if nodes_ptr != nodes_end continue looping
jne .LBB0_2
Also what if there are multiple sources? Do we cache every data() if size() is the same?
So, if u need index, there are indeed two and a half “good” options
- cache .data() and .size()
not exactly readable, not easy to maintain - use range based for, make index variable, increase manually
error prone, there could be continue in the middle - its ok to cache just .size()
data is still aliased
In daScript there is multiple source syntax, which can be used for multiple sources and indices:
for n1,n2 in arr1,arr2
...
for n,i in nodes,count(start,step) // or just count()
...
The upside is that iterators cache values. The downside is that each source is tested for the end of loop individually.
Jit manages to keep everything in registers.
AOT is an interesting story. Lets write the minimal framework necessary to simulate daScript Array and das_iterator:
#include <assert.h>
#define __forceinline inline
struct Node {
virtual void eval() = 0;
};
struct Context { };
struct Array {
char * data;
int size;
int lock;
};
template <typename TT>
struct TArray : Array { };
void array_lock ( Context & ctx, Array & arr ) { arr.lock ++; }
void array_unlock ( Context & ctx, Array & arr ) { assert(arr.lock); arr.lock --; }
template <typename TT>
struct das_iterator;
template <typename TT>
struct das_iterator<TArray<TT>> {
__forceinline das_iterator(TArray<TT> & r) {
that = &r;
array_end = (TT *)(that->data + that->size * sizeof(TT));
}
template <typename QQ>
__forceinline bool first(Context * __context__, QQ * & i) {
context = __context__;
array_lock(*__context__, *that);
i = (QQ *)that->data;
return i != (QQ *)array_end;
}
template <typename QQ>
__forceinline bool next(Context *, QQ * & i) {
i++; return i != (QQ *)array_end;
}
template <typename QQ>
__forceinline void close(Context * __context__, QQ * & i) {
array_unlock(*__context__, *that);
context = nullptr;
i = nullptr;
}
~das_iterator() {
TT * dummy = nullptr;
if (context) close(context, dummy);
}
Array * that;
TT * array_end;
Context * context = nullptr;
};
void eval ( TArray<Node *> & nodes, Context * __context__ ) {
das_iterator<TArray<Node *>> node(nodes);
Node ** n = nullptr;
bool needLoop = true;
needLoop = node.first(__context__, n) && needLoop;
for ( ; needLoop; needLoop = node.next(__context__,n) ) {
(*n)->eval();
}
node.close(__context__,n);
}
Things are good in the land of disassembler:
.LBB2_2:
mov rdi, qword ptr [r15 + rbx] // vtable_ptr = node_ptr
mov rax, qword ptr [rdi] // call_ptr = vtable_ptr[0]
call qword ptr [rax] // (*call_ptr)()
add rbx, 8 // node_ptr ++
cmp r12, rbx // if node_ptr != data.end() keep looping
jne .LBB2_2
Prologue and epilogue are slightly longer, but everything is in the registers.
count happens to be my daScript incantation of the day. Just add `count’ when you need index.
AOT recognizes it, JIT recognizes it. Its fast. It keeps disassembler happy.
To summarize when possible use daScript; it will do all those incantations for you.
For C++
- use range based loop when you can
- at least cache size when you can’t
- when writing performance critical C++ - cache everything
- reconsider rewriting in daScript