Graph redraw is very slow

[MohammadAlHajj]

I am using the graph to display ~1k vertexes and ~4k edges. I am having a very hard time making the graph redraw rate manageable. I am using multiple vertex decorators (Coulomb, Hook, Pin Center). I have not yet started adding edge decorators.

The problem is 2-fold. The first one is that the Coulomb Algorithm is O(n^2) complexity. The second is (and i am not sure how this works) that the algorithm is running single threaded. These things should be parallelizable. I don't know if and how they can be offloaded to the GPU/multithreaded. I am currently getting around 2 seconds per redraw per vertex on a Samsung A54. It is also causing the app to crash at this size of graph.

I am currently trying to implement a BarnesHutCoulombDecorator. This algorithm runs in O(nlog(n)) at the cost of negligible accuracy (half a pixel). I will be adding it as a pull request once i get the damn thing to work.

The other issue with parallelism might be implemented with isolates (not sure as i am new to flutter), but I have no way of plugging it in with the decorators that i can see. The decorators seem to work per vertex (GraphAlgorithm.compute(Vertex v, Graph graph) ) and i can't find a way to run the method on the whole graph/batch at once per redraw

Is there anything you can help me with? I don't really know if i am using the tool in the way you designed. My goal is to be able to handle 10K vertexes 50K edges at some point.

Finally, I am bashing my head against the lack of docs. I had to read whole classes to understand what some fields do. I would appreciate it if you can point me to anything that describes the workflow of the graph redraw/recalculation process. I think I get it, but i need some confirmation.

[CorvusYe]

You are right. This issue does indeed exist.

Recently, I have also been working on improving performance. We have just managed to increase the renderable level from the 1.x version by over 1k.

During the 2.x upgrade, it was initially planned to use isolate to transfer the computation process into parallel processing. However, it was felt that this might not yield results quickly, so the upgrade was prioritized for the current stage.

There is an option called perBatchTotal (default to 100) in the Options section. Adjusting this setting might have some impact on performance, but it won't resolve the underlying issue.

Currently, I only have a rough idea. In Options.run, the calculation process can be transferred to asynchronous execution, or the compute API can be completely changed.

Unfortunately, there have been other ongoing matters recently that may prevent me from dedicating sufficient time to further enhance performance.

[MohammadAlHajj]

Right now, the animation controller runsOptions.run every frame, and restarts every 10 seconds.

• There is no check if the last run is completed or not before the next execution.
• Each run is responsible for a certain batch size (default of 100). By design, this forces a fixed rate of 3k vertexes at 30FPS

If you move to background parallel execution of algorithms, you don't have to wait at all. just keep the algorithm running on all the time, and update whatever it have ready at the next frame tick.

A possible sideeffect: if the previous frame's calculation is not done, will that:

1. queue the new frame's calculations into "next batch queue"
2. or stop old calculations and start the new ones.

If (1) happens, will that cause memory problems because the queue keeps getting bigger, or will it try executing multiple batches ate the same time and cause the processor to be overwhelmed? I have had a lot of crashes when the graph grew in size.
If (2) happens, will that cause some calculations to not be executed and vertexes to not be recalculated?

[CorvusYe]

If (2) happens, there may indeed be some vertexes that cannot be updated.

if (1) happens, can new tasks be pushed into the queue after each frame ends. There is too much backlog of tasks, and updating the view does not have much significance.

I prefer: parallel processing of different batches and serial processing of different frames.
Because the operation of the current frame still depends on the new position of the node in the previous frame, if the old position is continuously used in parallel, there may be some unnecessary computational load.

I'm not sure if I understand the situation you encountered correctly. If the understanding is not correct, further communication can be conducted.

[MohammadAlHajj]

Isolates will need a major redesign

1. Graphs are not passable between isolates:
   I tried Isolates. Isolates need to interact using ReceivePort, and SendPort. SendPort.send is used to send a message, but there are limitations on what the message can hold. One of these rejected Items in the message is "Path" (dart:ui). Edge has a Path? path field in it. Graph has a list of edges => Graph is not passable. I attached the exception stack below.

======== Exception caught by animation library =====================================================
The following ArgumentError was thrown while notifying listeners for AnimationController:
Invalid argument(s): Illegal argument in isolate message: object is unsendable - Library:'dart:ui' Class: _NativePath@17065589 (see restrictions listed at `SendPort.send()` documentation for more information)
 <- path in Instance of 'Edge' (from package:flutter_graph_view/model//edge.dart)
 <- _List len:4 (from dart:core)
 <- _Set len:3 (from dart:_compact_hash)
 <- Instance of 'Vertex<dynamic>' (from package:flutter_graph_view/model/vertex.dart)
 <- _List len:64 (from dart:core)
 <- _Set len:39 (from dart:_compact_hash)
 <- Instance of 'Vertex<dynamic>' (from package:flutter_graph_view/model/vertex.dart)
 <- _List len:64 (from dart:core)
 <- _Set len:56 (from dart:_compact_hash)
 <- Instance of 'Vertex<dynamic>' (from package:flutter_graph_view/model/vertex.dart)
 <- end in Instance of 'Edge' (from package:flutter_graph_view/model//edge.dart)
 <- _List len:3 (from dart:core)
 <- Instance(length:1) of '_GrowableList' (from dart:core)
 <- _List len:8192 (from dart:core)
 <- _Map len:3361 (from dart:_compact_hash)
 <- edgesBetweenHash in Instance of 'Graph<dynamic>' (from package:flutter_graph_view/model/graph.dart)
 <- graph in Instance of '_IsolateInitMessage' (from package:remind_me_again/core/ui/flutter_graph_view/graph_algorithm/isolate_force_algorithm.dart)

When the exception was thrown, this was the stack: 
#0      _SendPort._sendInternal (dart:isolate-patch/isolate_patch.dart:259:43)
#1      _SendPort.send (dart:isolate-patch/isolate_patch.dart:240:5)
#2      IsolateForceAlgorithm.compute (package:remind_me_again/core/ui/flutter_graph_view/graph_algorithm/isolate_force_algorithm.dart:181:31)
#3      GraphAlgorithm.compute (package:flutter_graph_view/core/graph_algorithm.dart:152:19)
#4      RandomOrPersistenceAlgorithm.compute (package:flutter_graph_view/core/algorithm/random_or_persistence_algorithm.dart:24:11)
#5      Options.run (package:flutter_graph_view/core/options.dart:189:24)
#6      _GraphComponentCanvasCustomState.run (package:remind_me_again/core/ui/flutter_graph_view/CraphComponentCanvasCustom.dart:55:13)
#7      AnimationLocalListenersMixin.notifyListeners (package:flutter/src/animation/listener_helpers.dart:160:19)
#8      AnimationController._tick (package:flutter/src/animation/animation_controller.dart:957:5)
#9      Ticker._tick (package:flutter/src/scheduler/ticker.dart:269:12)
#10     SchedulerBinding._invokeFrameCallback (package:flutter/src/scheduler/binding.dart:1434:15)
#11     SchedulerBinding.handleBeginFrame.<anonymous closure> (package:flutter/src/scheduler/binding.dart:1265:11)
#12     _LinkedHashMapMixin.forEach (dart:_compact_hash:764:13)
#13     SchedulerBinding.handleBeginFrame (package:flutter/src/scheduler/binding.dart:1263:17)
#14     SchedulerBinding._handleBeginFrame (package:flutter/src/scheduler/binding.dart:1179:5)
#15     _invoke1 (dart:ui/hooks.dart:346:13)
#16     PlatformDispatcher._beginFrame (dart:ui/platform_dispatcher.dart:426:5)
#17     _beginFrame (dart:ui/hooks.dart:291:31)
The AnimationController notifying listeners was: AnimationController#dc8cb(▶ 0.024)
====================================================================================================

2. Serialization is not practical:
   The other way to do the message passing is by serializing and decentralizing the data on every message call. Deserialization is possible using MapConvertor.convertGraph. Serialization is currently not implemented. This will cause 2 problems. The smaller one is that this process will be very heavy to do especially with large graphs. This makes it counter-intuitive. The large problem is that even if we fixed the Serialization/Deserialization the graph that we have in the worker isolate is different from the 'main UI isolate`. This will mean that the GraphAlgorithm.compute will not be updating the original vertexes, only the copies.

3. The current implementation forces using GraphAlgorithm.compute
   There is no other way of calculating the new force except through GraphAlgorithm.compute, and GraphAlgorithm.compute needs a Vertex and a Graph. This goes back to problem (2)

Solutions:

1. Use something other than Isolates. I don't know if isolate_agents is useful. flutter docs reference it.
2. add a GraphAlgorithm static function that does the calculations and pass the required data as a Map of primitives, and force GraphAlgorithm.compute to use it to do the actual computation. We need this to force the same calculation from both functions.

[CorvusYe]

I previously used isolate_manager, and we encountered a similar issue.

If we extract the ID, radius, and position and put them into a static function, then after the calculation is complete, we can use the ID to find the vertex and assign the position to it. Numbers and strings can be used as messages.

I'm not sure if this approach is feasible.

[CorvusYe]

However, it is unavoidable that either option might necessitate changes to the way compute methods are called, and the decorators would need to be modified accordingly.

[MohammadAlHajj]

This is a quick and dirty way of doing it. This is just psudo code. I honestly hate it:

abstract class GraphAlgorithm {

  /// ......

  /// Position setter.
  ///
  /// 对节点进行定位设值
  @mustCallSuper
  void compute(Vertex v, Graph graph) {
    if (decorators != null) {
      for (var decorator in decorators!) {
        if (!decorator.needContinue(v)) return;
        decorator.compute(v, graph);
      }
    }
    // call dumb calculator only for self, children have already been processed 
    decorator.computeForce(
        v.data,
        graph.data,
        decoratorData: null,
        computeChildDecorators: false
    );
  }


  /// dumb calculator for current decorator and children.
  static Vector2 computeForce(
    Map vertex,
    Map<String, Map> graph
    {Map<String, Map>? decoratorData,
    computeChildDecorators = true}
  ) {
    Vector2 force = Vector2.zero();
    if (decoratorData == null || !computeChildDecorators){
      // child decorators exist
      List<GraphAlgorithm> decorators =
      );
      for (var decorator in decorators) {
        if (!decorator.needContinue(v)) {
            return;
        }
        final decoratorType = cedecoratorData["decoratorType"] as String)
        /// somehow find out the type of the decorator. I hate this implementation
        force += switch (decoratorType){
          case ABC: ABC.computeForce(
              vertex,
              graph,
              decoratorData: decorator,
              computeChildDecorators = true );
          /// case ...
        }
      }
    }

    return force + forceFormulaCalc(/* current decorator params*/);
  }

  /// actual formula calculation
  static Vector2 forceFormulaCalc(Map DecoratorParams){}

  Map<String, Map> serialize(){
    // not implemented
    // decoratorData["decoratorType"] = "String or Enum type"
  }

  /// T is the current Class Type
  static T deserialize<T>(Map<String, Map> data){
    // not implemented
  }

  /// ......
}

[CorvusYe]

It might be possible to refactor the existing implementation after verifying that using the isolate results in significant performance improvements.

My point is that sometimes focusing too early on elegance while neglecting the core requirements can be counterproductive.

However, if it is confirmed that significant improvements can be achieved, it would indeed be best to start with an elegant and efficient approach from the outset.

[MohammadAlHajj]

@CorvusYe I though about this a lot and conversed with a colleague. The current way of calculating is not parallelizable.

The current way is to calculate and move a vertex (X) and move to the next one (Y). That means that vertex Y has to wait for X to be done, and Z will have to wait for Y and so on....

The new flow should be:

• calculate all vertexes forces (without applying them)
• apply Motion Decorator on the whole graph all at once
• apply the rest of the decorators (PauseDecorator, TimeCounterDecorator, LegendDecorator, ...). I feel like these should be separate anyways

If we want to parallelize, we have to remove the dependence of vertexes on each others' position per 1 redraw of the whole graph. We will have to use the position recalculation of the whole graph as our starting point. The decorators concept will have to be changed.

having all the force decorators use the same starting state (the last calculated position of the whole graph) will then allow us to parallelize. A big chunk of how the library works will have to be rewritten.

current Options.run:

  run() {
    if (graph.vertexes.isEmpty) return;
    var g = currantBatchRange();
    var vertexs = graph.vertexes.sublist(g[0], g[1]);
    for (var vertex in vertexs) {
      graph.algorithm?.compute(vertex, graph);
    }
    batchIndex++;
  }

[CorvusYe]

I completely agree with you and your colleagues.
At present, the limitation of mutual constraint between nodes in this computing method is too great, which brings certain difficulties to parallel computing. Even if these functional decorations are separated, it cannot fundamentally change this constraint relationship.

That's also why I said before:

or the compute API can be completely changed.

I just haven't thought about whether this kind of modification also needs to overturn the system of decorators.

For the order of 10k, I have seen a very smooth solution before. Perhaps we can gain some inspiration from its source code.
https://echarts.apache.org/examples/en/editor.html?c=graphgl-npm-dep&gl=1&theme=dark

At present, one of my applications is also limited in performance, and in the recent stage, it can only increase the scale from hundreds to thousands. So I also want to know how to increase the scale from 1k to 10k.

[MohammadAlHajj]

Hi. I have some good news. I need your help to verify something. How do we do this? Do you create a test branch here and i merge into it or do you pull from my repo?

[CorvusYe]

@MohammadAlHajj
It's an exciting piece of news.
I prefer to directly pull from your code repository and then merge it into the main branch.
This should make it easier for you to develop the project into something even more popular in the future.

[MohammadAlHajj]

the solution is only a proof of concept. It is still has technical issues i want to talk to you about. I need advice on how to deal with these issues in flutter. It is not a very friendly language for this kind of problem. Is there a way that we can talk about it in a more direct way?

[CorvusYe]

What kind of problem is it? I'll see if I can try to help you.
Regarding communication methods, email or do you use WeChat there ?

[oscarshaitan]

Hello any update? from 1k vertex the graph is getting super slow and you can see my worst case in the image