Hi,
I found some like the code following may affect performance( Time complexity is
O(n) ):
private int getMaxPartition() {
int maxPartition = 0;
for(InMemoryPartition<T> p1 : this.partitions) {
if(p1.getBlockCount() > maxPartition) {
maxPartition = p1.getBlockCount();
}
}
return maxPartition;
}
These codes is in the FLINK-RUNTIME and may be called many times when flink
runs.
As I learned, querying a max(min) number from a set of numbers can be optimized
into O(log(n)) even O(1) ( .i.e RMQ, heap, segment tree, treap…. ).
And there is a thought of mine:
Using TreeMap as a Temporary storage for the size of partition pages.
Key stands for the size of partition pages.
Value stands for the count of the same size.
The TreeMap will synchronous update when this.partitions adds or removes a
element.
So we can just use TreeMap.lastKey() as the maxPartition(TreeMap.firstKey() as
the minPartition).
And all the operations(put, remove, lastKey, firstKey) in TreeMap cost
O(log(n)).
If getMaxPartition() is called many times, this may improve performance.
And I am here looking for your opinions.
Greetings,
Huang Wei
华为技术有限公司 Huawei Technologies Co., Ltd.
Tel:+86 18106512602
Email:huangwei...@huawei.com
