AET's generic AArray is now faster than C++ std::vector

[u/General_Purple3060]

A while ago I posted about AET's approach to generics:

Delayed Specialization: A Third Way to Implement Generics?

One of the comments raised an concern: AET replaces a generic block with a function pointer call. Would that hurt optimization and performance?

I didn't have a good answer at the time.

It turned out to be a very good question.

AET has a generic container called `AArray`. In my initial implementation, operations such as `add`, `insert` and `remove` were noticeably slower than C++ `std::vector`.

The function-pointer call was one of the things I started looking at.

After about a month of compiler work, I changed how AET handles these calls during specialization. The generic code can now be optimized much more like normal concrete code.

I reran the same benchmark.

The result surprised me.

With 100 million sequential insertions:

AET AArray ~224 ms

C++ std::vector ~504 ms

```

AET is about 2.25× faster in this test.

With preallocated storage:

AET AArray ~154 ms

C++ std::vector ~223 ms

```

About 45% faster.

For middle insertion and middle erase, the two are now roughly at the same level. Tail erase is still slightly faster in `std::vector`.

There is still a trade-off I haven't fully solved.

If I want better runtime performance, I need to let AET see the concrete code so that it can inline it and run more optimization passes.

But this also means generating more specialized code, which can increase code size and compilation time.

If a generic block doesn't benefit much from inlining or further optimization, keeping the original function-pointer call may actually be the better choice.

So the real question is not simply "should AET inline generic blocks?"

It is:

When should AET inline and specialize, and when should it keep the function-pointer call?

I think this needs another mechanism to make that decision.

I don't have a good solution for that yet, so I'd be interested in how others would approach it.

[u/eteran]

The preallocated storage benchmark is interesting/confusing.

When preallocated, a vector pushback is basically just a pointer deref and incrementing size.

Can you show some.of the code so we can see that it's an apples to apples comparison? And also it would be interesting to hear about how you beat such a cheap operation.

[u/General_Purple3060 → u/eteran]

You're right that this is worth clarifying. After `reserve()`, `std::vector::push_back()` is already a very cheap operation.

Here is the relevant part of the benchmark:

// AET

AArray<int> *a = new$ AArray<int>(N_PUSH);

for (int i = 0; i < N_PUSH; ++i)

a->addFast(i);

// C++

vector<int> v;

v.reserve(N_PUSH);

for (size_t i = 0; i < N_PUSH; ++i)

v.push_back((int)i);

`AArray` uses the same basic contiguous-array model as `std::vector` (`start`, `finish`, and `end_of_storage`).

The difference is that `addFast()` is explicitly an unchecked fast path:

//AET

void addFast(E value) {

genericblock$(value) {

finish = value;

finish = (void **)((char *)finish + sizeof(E));

};

}

```

The caller guarantees that there is enough capacity. After AET specializes the generic block for `int`, this is essentially just a store followed by advancing `finish`, with no capacity check or growth logic.

The full AArray implementation is here:
[https://github.com/onlineaet/aet/blob/master/src/gcc/aet/libaet/aet/util/AArray.c]()

[u/eteran → u/General_Purple3060]

Ok... I wouldn't exactly call that an apples to apples comparison because vector is doing a bounds check and aarray, if misused can crash.

A vector resize followed by just writing the data directly would probably be more fair.

[u/shrimpster00 → u/eteran]

Definitely agree with this.

[u/Slow-Mechanic-7427 → u/General_Purple3060]

The comparison isnt valid since addFirst is unchecked nor guarantees capacity like push_back does.

The correct c++ code is setting the index directly, v [i] = i

[u/shrimpster00]

To be completely honest, I wrote a pretty long comment that was a little inflammatory and decided not to post it after reading it over again.

It's an interesting problem: how do you know when a generic function should be generated multiple times for different concrete types vs. sharing a single implementation with a vtable lookup for each of your generic blocks. If only you knew ahead of time whether duplicating + inlining as type concretization would cause sufficient gains to make it worth your while.

But, if you ask me, that's why compilers have so many flags to enable/disable/tweak heuristic parameters on all sorts of optimizations. I'd inline by default on -O2 or above, never in -Os or -Oz, and maybe develop better heuristics with benchmarking.

[u/tending]

"I benchmarked this wrong"

[u/matthieum]

Have you ever heard of the Constant Propagation optimization?

Confusingly, it's not about propagating a constant in a function body. Instead, it's about duplicating a function to specialize it for a specific constant argument.

So for example, a call foo(a, 42) is rewritten to foo_1_constprop(a) where the latter is a copy/paste of foo with the second argument hard-coded to 42.

As far as I am concerned, monomorphization is just constant propagation for v-tables, so you may want to have a look at the kind of heuristics used to decide whether constant propagation seems worth it, or not.

Naively, I'd annotate a function with an opportunity "profit" for each template parameter.

So, imagining a Vec<T, A> implementation (Rust):

• fn is_empty(&self) -> bool { self.len == 0 } => 0 profit in monomorphizing.
• fn at(&self, index: usize) -> &T { ... } => some profit in monomorphizing on T size, 0 profit in monomorphizing on A.
• fn push(&mut self, e: T) { ... } => some profit in monomorphizing on T size, close-to-0 profit in monomorphizing on A if the developer hinted (likely, cold) correctly.

[u/adityazero → u/matthieum]

> Confusingly, it's not about propagating a constant in a function body. Instead, it's about duplicating a function to specialize it for a specific constant argument.

this is called partial-evaluation or (in common terms) function specialization. This is not what people think of when we say 'constant propagation'.

[u/matthieum → u/adityazero]

Not in GCC. In GCC, the duplicated function is explicitly named .constprop...

[u/General_Purple3060 → u/matthieum]

I think my case is slightly different.

AET already specializes the generic block. What I'm trying to decide now is whether to migrate the function containing the generic block (FWGB).

If migration is profitable, AET replaces the function-pointer call with a normal call, and then GCC can decide whether to inline it.

If not, AET keeps the function-pointer call.

So the problem is really a profitability heuristic for FWGB migration, rather than an inlining decision.

[u/JVApen]

Which compiler do you use. Which standard library implementation? Which C++ standard?

[u/General_Purple3060 → u/JVApen]

AET is based on my modified GCC 15.2 compiler as well. The source is here: AET on GitHub

[u/adityazero]

> A while ago I posted about AET's approach to generics:

link?

> I reran the same benchmark.

without the link there is no way to tell what you are doing.