One: [onert] Improvement performance of OpSequences::findOperation

[periannath]

This issue comes from https://github.com/Samsung/ONE/issues/2610#issuecomment-649280855

OpSequences::findOperation traverses whole operations to find target operation.

It seems that function can be optimized in many ways.

1. Early stop when operation is found
2. Create table.
3. ...

I'll implement options and compare the performance.

• [x] Implement early stop when operation is found
• [x] Implement creation of table
• [x] Compare performance
• [x] Upload PRs #2678 #2816

[periannath]

Testing early stop

Master

https://github.com/Samsung/ONE/blob/52bc738295f267dd75c265e9cee3e5ff1e855a06/runtime/onert/core/src/ir/OpSequences.cc#L73-L84

• Prepare time : 1533 ms

Trial 1 : Add return function

     for (const auto &op_idx : object.operations())
     {
       if (op_idx == operation_index)
+      {
         ret = index;
+        return;
+      }
     }
   });
   return ret;

• Prepare time : 1060 ms

[periannath]

Testing early stop (cont'd)

Trial 2 : Access operations directly instead of using iterate function

• iterate function always traverse whole OpSequences
• Some OpSequence searches can be skipped by accessing the operations directly

  OpSequenceIndex ret;
  for (auto &e : _objects)
  {
    OpSequence &object = *e.second;
    auto it = find(object.operations().begin(), object.operations().end(), operation_index);
    if (it != object.operations().end())
     {
      ret = e.first;
      return ret;
     }
  }
  return ret;

• Prepare time : 683 ms

[periannath]

How to implement OperandIndex to OpSequenceIndex table?

1. Managing Table at OpSequences class
   
   
   
   1. Crating table entry when OpSequence is inserted
      
      
      
      
      
      • At this point, OpSequence has one operation
      
      
      
      • Operations added by OpSequence::appendOperation are untrackable
      
      
      
   
   
   2. Cache entry when findOperation is executed
      
      
      
      
      
      • findOperation is const member function
      
      
      
      • Unable to create cache entry
      
      
      
   
   
2. Managing Table at OpSequence class
   
   
   
   • findOperation should traverse OpSequences
   
   
   • Small performance improvement
   
   

[periannath]

Testing map

• Tried option 1 https://github.com/Samsung/ONE/issues/2655#issuecomment-650047629
• Create sequence_index map in OpSequences class
  
  
  
  • Cache sequence_index when OpSequence is added to OpSequences
  
  
  • Cache entry when findOperation is executed
  
  
  • Set mutable for map
  
  

  mutable std::unordered_map<OperationIndex, OpSequenceIndex> _seq_indexes;

• Prepare time : 435 ms

[periannath]

All related PRs merged.