Skip to content

tsort: drastically reduce memory copies#5969

Merged
sylvestre merged 1 commit intouutils:mainfrom
tertsdiepraam:tsort-opt
Feb 11, 2024
Merged

tsort: drastically reduce memory copies#5969
sylvestre merged 1 commit intouutils:mainfrom
tertsdiepraam:tsort-opt

Conversation

@tertsdiepraam
Copy link
Copy Markdown
Collaborator

@tertsdiepraam tertsdiepraam commented Feb 11, 2024 •
edited
Loading

To reduce the copying happening in tsort, we can load the entire input in memory and only refer to slices within that input instead of allocating a String for each occurrence of a node.

cc @anastygnome

On my input generated with:

import random

random.seed(0)

N = 10000
for i in range(100*N):
    a = random.randint(0,N)
    b = random.randint(0,N)
    if a != b:
        print(f"{min(a, b)} {max(a, b)}")

The time measured with hyperfine drops from ~2.3 seconds to ~1.6 seconds.

@anastygnome
Copy link
Copy Markdown
Contributor

anastygnome commented Feb 11, 2024

Nice, please set a fixed seed for reproducibility tho :)

@tertsdiepraam
Copy link
Copy Markdown
Collaborator Author

tertsdiepraam commented Feb 11, 2024

Fair :)

@sylvestre sylvestre merged commit e3c10bc into uutils:main Feb 11, 2024
@chenrui333 chenrui333 mentioned this pull request Mar 24, 2024
Merged
@moonfruit moonfruit mentioned this pull request Mar 28, 2024
Merged
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Reviewers

No reviews

Assignees

No one assigned

Labels

None yet

Projects

None yet

Milestone

No milestone

Development

Successfully merging this pull request may close these issues.

3 participants

@tertsdiepraam @anastygnome @sylvestre