Thakns for details. Arfer another small benchmark, it appeared that addition to AA is 10x times slower than removal from it. So that's why (2) isn't so bad in my previous tests - most of time AA was adding elements to remove later. Anyway if (2) also reallocates it's much much worse that (1).