Skip to content

Performance: Improve EdgeList #3400

@lvca

Description

@lvca

Currently each vertex has a pointer to a Linked List for out and in edges. All the edges are in this linked list ordered LIFO (last edge inserted is the first). This is not optimal for the following operations:

  • count all edges -> browse the entire linked list
  • count edges of a specific type -> browse the entire linked list
  • traverse edges of one edge type only -> browse the entire linked list
  • browse edges FIFO (from the oldest)

We'd need to use v1 (from v0, the original format) with the following improvements:

  • store edge count (4 bytes - up to 4B edges) in the head of the linked list
  • separate the linked list in multiple ones, one per edge type (or bucket)
  • save the pointer to the 1st segment to browse FIFO

Metadata

Metadata

Assignees

Labels

Projects

No projects

Milestone

No milestone

Relationships

None yet

Development

No branches or pull requests

Issue actions