Allocate intermediate values on the heap in [std]

Open
#56 4 comments 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

Assessment

Difficulty
5/5
Estimated time
Over a week
Newbie friendliness
38/100
Issue type
Refactor
Clarity
Mostly clear
Activity status
Quiet
Tech stack
rust
Domain
operating-systems, performance

Research direction

Start by reviewing dependency #49 and the std/no_std setup for the mlsda and mlkem algorithm crates. Use valgrind --tool=massif to compare stack and heap usage with a release-branch baseline. Done means large intermediate values use the heap when std is available, stack usage is reduced, and stack-versus-heap control for key structs is documented.

Written by the indexing model from the issue text.

Description

enhancement research

Depends on #49

Having made all our algorithm crates work in a stack-only [no_std] build, let's now go back and make use of our feature = 'std' so that algorithms like mlsda and mlkem allocate large intermediate values such as vectors and matrices on the heap when available.

The reason for this is that most operating systems enforce strict stack-size limits -- ex.: an entire process will get killed if it uses more than 8 mb of stack. If you're not careful, you can blow this just by creating a bunch of ML-DSA-87 keys. So if we have access to a memory allocator, it's probably polite to use it.

There is a research task here in that I'm not actually sure how to force the usage of heap vs stack when declaring variables. Is that what Box<> is for? Is it as simple as putting a cargo feature guard on the crate-level #![no_std] line, and the compiler will do the rest for us?

Also, some of our simple structs (ex.: public and private key types) will need some documentation for how the caller can control whether they get allocated on the stack or on the heap.

Acceptance criteria: test with

valgrind --tool=massif

to make sure that we're seeing the big allocations move to the heap, and the total stack usage go down (might be worth taking a before-snapshot on the release branch to compare araignst)

Dominant language
Rust
Stars
25
Forks
18
Avg merge
16h 38m
Merged PRs (30d)
3

Contributor guide

Open the contributing guide

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

More from bcgit/bc-rust

All issues in bcgit/bc-rust

Similar issues

More Rust issues

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.