Zhilong Hong created FLINK-22767:
------------------------------------
Summary: Optimize the initialization of
ExecutionSlotSharingGroupBuilder
Key: FLINK-22767
URL: https://issues.apache.org/jira/browse/FLINK-22767
Project: Flink
Issue Type: Sub-task
Components: Runtime / Coordination
Affects Versions: 1.13.0
Reporter: Zhilong Hong
Based on the scheduler benchmark introduced in FLINK-21731, we find that during
the initialization of ExecutionSlotSharingGroupBuilder, there's a procedure
that has O(N^2) complexity:
{{ExecutionSlotSharingGroupBuilder#tryFindAvailableProducerExecutionSlotSharingGroupFor}}.
This initialization happens during the initialization of
LocalInputPreferredSlotSharingStrategy.
The original implementation is:
{code:java}
for all SchedulingExecutionVertex in DefaultScheduler:
for all consumed SchedulingResultPartition of the SchedulingExecutionVertex:
get the result partition's producer vertex and determine the
ExecutionSlotSharingGroup where the producer vertex locates is available for
current vertex{code}
This procedure has O(N^2) complexity.
It's obvious that the result partitions in the same ConsumedPartitionGroup have
the same producer vertex. So we can just iterate over the
ConsumedPartitionGroups instead of all the consumed partitions. This will
decrease the complexity from O(N^2) to O(N).
The optimization of this procedure will speed up the initialization of
DefaultScheduler. It will accelerate the submission of a new job, especially
for OLAP jobs.
--
This message was sent by Atlassian Jira
(v8.3.4#803005)
