Skip to content

⚡ Faster FFD packing #3537

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom
Merged
merged 4 commits into from
Jun 4, 2025
Merged

⚡ Faster FFD packing #3537

merged 4 commits into from
Jun 4, 2025

Conversation

mariosasko
Copy link
Contributor

@mariosasko mariosasko commented Jun 4, 2025 •
edited
Loading

What does this PR do?

This PR speeds up the FFD packing implementation by using the pyarrow.compute API instead of numpy and a segment tree structure for efficient bin size querying (the time complexity goes down from O(batch_size * seq_length) to O(batch_size * log(seq_length))).

These are the benchmark results (≈ 3.5 faster; the benchmark comes from #3521):

Benchmark

main

Map: 100%|████████████████████████████████| 100000/100000 [00:01<00:00, 75716.17 examples/s]
Map: 100%|████████████████████████████████| 100000/100000 [00:01<00:00, 73297.02 examples/s]
Map: 100%|████████████████████████████████| 100000/100000 [00:01<00:00, 74549.33 examples/s]
Map: 100%|████████████████████████████████| 100000/100000 [00:01<00:00, 76940.53 examples/s]
Map: 100%|████████████████████████████████| 100000/100000 [00:01<00:00, 75127.88 examples/s]
Map: 100%|██████████████████████████████| 100000/100000 [00:00<00:00, 4256404.95 examples/s]
Map: 100%|██████████████████████████████| 100000/100000 [00:00<00:00, 5455295.57 examples/s]
Map: 100%|██████████████████████████████| 100000/100000 [00:00<00:00, 5456715.02 examples/s]
Map: 100%|██████████████████████████████| 100000/100000 [00:00<00:00, 5559566.83 examples/s]
Map: 100%|██████████████████████████████| 100000/100000 [00:00<00:00, 5592852.76 examples/s]
Time for 100k rows with FFD strategy: 6.6822 seconds
Time for 100k rows with Fixed strategy: 0.1003 seconds

#3524

Map: 100%|████████████████████████████████| 100000/100000 [00:01<00:00, 81261.81 examples/s]
Map: 100%|████████████████████████████████| 100000/100000 [00:01<00:00, 85652.81 examples/s]
Map: 100%|████████████████████████████████| 100000/100000 [00:01<00:00, 83580.96 examples/s]
Map: 100%|████████████████████████████████| 100000/100000 [00:01<00:00, 83832.56 examples/s]
Map: 100%|████████████████████████████████| 100000/100000 [00:01<00:00, 76309.26 examples/s]
Map: 100%|██████████████████████████████| 100000/100000 [00:00<00:00, 4284886.50 examples/s]
Map: 100%|██████████████████████████████| 100000/100000 [00:00<00:00, 3932184.58 examples/s]
Map: 100%|██████████████████████████████| 100000/100000 [00:00<00:00, 4561157.93 examples/s]
Map: 100%|██████████████████████████████| 100000/100000 [00:00<00:00, 5008243.78 examples/s]
Map: 100%|██████████████████████████████| 100000/100000 [00:00<00:00, 4431055.28 examples/s]
Time for 100k rows with FFD strategy: 6.1274 seconds
Time for 100k rows with Fixed strategy: 0.1206 seconds

this version

Map: 100%|███████████████████████████████| 100000/100000 [00:00<00:00, 263725.03 examples/s]
Map: 100%|███████████████████████████████| 100000/100000 [00:00<00:00, 273755.15 examples/s]
Map: 100%|███████████████████████████████| 100000/100000 [00:00<00:00, 273193.66 examples/s]
Map: 100%|███████████████████████████████| 100000/100000 [00:00<00:00, 274199.35 examples/s]
Map: 100%|███████████████████████████████| 100000/100000 [00:00<00:00, 235434.80 examples/s]
Map: 100%|██████████████████████████████| 100000/100000 [00:00<00:00, 5169346.05 examples/s]
Map: 100%|██████████████████████████████| 100000/100000 [00:00<00:00, 5535938.76 examples/s]
Map: 100%|██████████████████████████████| 100000/100000 [00:00<00:00, 4859749.50 examples/s]
Map: 100%|██████████████████████████████| 100000/100000 [00:00<00:00, 5188080.90 examples/s]
Map: 100%|██████████████████████████████| 100000/100000 [00:00<00:00, 5300590.18 examples/s]
Time for 100k rows with FFD strategy: 1.9232 seconds
Time for 100k rows with Fixed strategy: 0.1010 seconds

Additionally, I ran a benchmark on the tokenized Alpaca dataset, and the speed-up there is even more significant with larger seq_len.

Before submitting

  • This PR fixes a typo or improves the docs (you can dismiss the other checks if that's the case).
  • Did you read the contributor guideline,
    Pull Request section?
  • Was this discussed/approved via a GitHub issue? Please add a link
    to it if that's the case.
  • Did you make sure to update the documentation with your changes?
  • Did you write any new necessary tests?

Who can review?

Anyone in the community is free to review the PR once the tests have passed. Feel free to tag
members/contributors who may be interested in your PR.

@HuggingFaceDocBuilderDev
Copy link

The docs for this PR live here. All of your documentation changes will be reflected on that endpoint. The docs are available until 30 days after the last update.

@qgallouedec
Copy link
Member

Fantastic optimization! Thank you!

Don't worry about the CI, it's not related to your PR

@qgallouedec qgallouedec changed the title Faster FFD packing ⚡ Faster FFD packing Jun 4, 2025
@qgallouedec qgallouedec merged commit 50a2fa8 into huggingface:main Jun 4, 2025
10 checks passed
@mariosasko mariosasko deleted the faster-ffd branch June 11, 2025 18:35
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Reviewers

@qgallouedec qgallouedec qgallouedec approved these changes

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
@mariosasko @HuggingFaceDocBuilderDev @qgallouedec