Remove the usage of VLAs in the code by thufschmitt · Pull Request #7348 · NixOS/nix

thufschmitt · 2022-11-25T19:34:41Z

Although Variable-length arrays are allowed by the C standard, they are frowned
upon, and aren't valid C++ (gcc accepts them a non-standard extension) and clang apparently does the same which is why they work here). So better get rid of them altogether.

Depends on #7346.

src/libexpr/eval.cc

src/libexpr/primops.cc

edolstra · 2022-11-25T20:45:54Z

I think statically sized arrays or small_vector should be avoided in functions that can be executed recursively. E.g.

                Value * vArgs[64];

in callFunction() adds 512 bytes of stack space to function calls, which adds up quickly for deeply recursive Nix code.

To be honest I don't really share the concerns over VLAs. We've used them for years without any issues. The zero-length VLA issue seems a bit language lawyering.

nixos-discourse · 2022-12-12T10:03:53Z

This pull request has been mentioned on NixOS Discourse. There might be relevant details there:

https://discourse.nixos.org/t/2022-12-09-nix-team-meeting-minutes-15/23951/1

tomberek · 2022-12-19T12:40:14Z

TODO (from meeting):

check eval impacts
update stack overflow test

fricklerhandwerk · 2022-12-19T17:19:44Z

Discussed in Nix team meeting 2022-12-19:

@edolstra: we have a test that checks the stack, but it's disabled because it blows the stack
@thufschmitt will add benchmarks to test evaluation speed.

nixos-discourse · 2022-12-19T17:23:15Z

This pull request has been mentioned on NixOS Discourse. There might be relevant details there:

https://discourse.nixos.org/t/2022-12-19-nix-team-meeting-minutes-18/24121/1

VLAs are a dangerous feature, and their usage triggers an undefined behavior since theire size can be zero in some cases. So replace them with `boost::small_vector`s which fit the same goal but are safer. It's also incidentally consistently 1% faster on the benchmarks.

There's generally no strict reason for using them, and they are somewhat fishy, so let's avoid them.

roberth · 2023-11-16T12:30:38Z

I think statically sized arrays or small_vector should be avoided in functions that can be executed recursively.

I've reduced the numbers significantly. Most significantly, 4 is enough for normal lambda calls. I expect the primops to contribute less to stack depth by number of nested invocations, so these use larger numbers, albeit reduced from what was originally in the PR.
This reduction is fine, because for large numbers the allocation is amortized to insignificance, and in many cases the data size is small anyway.

TODO (from meeting):

check eval impacts

This is infinitely faster on expressions where these VLAs caused stack overflows.

update stack overflow test

I find this somewhat pointless since the code does not allocate variable amounts of stack space anymore. Yes, tests are good, but these would be expensive, especially in terms of maintaining them because it involves developing non-trivial test support code for it. Silvan could attest that this is non-trivial. I'd rather focus that effort on more impactful testing improvements.

roberth · 2023-11-16T12:31:39Z

bug label: Fixes a stack overflow: NixOS/nixpkgs#214021 (comment)

thufschmitt

Thanks for taking over this @roberth !

Looks good to me, although I think this deserves some benchmarks (IIRC, the original version had a small impact depending on the sizes chosen)

src/libexpr/eval.cc

src/libexpr/eval.hh

This makes stack usage significantly more compact, allowing larger amounts of data to be processed on the same stack. PrimOp functions with more than 8 positional (curried) arguments should use an attrset instead.

Clang warned that the expanded code used to have a buffer overflow. Very strange, but also very avoidable.

Try to stay away from stack overflows. These small vectors use stack space. Most instances will not need to allocate because in general most things are small, and large things are worth heap allocating. 16 * 3 * word = 384 bytes is still quite a bit, but these functions tend not to be part of deep recursions.

128 is still beyond the point where the allocation overhead is insignificant, but we don't anticipate to overflow for these use cases, so it's fine.

roberth · 2023-11-16T14:40:31Z

deserves some benchmarks

That would be great, but I can only treat this as a bugfix unfortunately.
Based on your earlier measurement I feel confident that this is not a performance regression.

thufschmitt · 2023-11-16T18:05:31Z

Based on your earlier measurement I feel confident that this is not a performance regression.

I wasn't, but I hyperfined it and there's zero visible difference on nix search nixpkgs firefox. So I should have 😛

edolstra · 2023-11-17T13:07:03Z

This broke the buildNoGC job: https://hydra.nixos.org/build/241067941 which is blocking the new release.

roberth · 2023-11-17T17:17:01Z

This broke the buildNoGC job: https://hydra.nixos.org/build/241067941 which is blocking the new release.

Fixed in Fix buildNoGc #9374

Remove the usage of VLAs in the code (cherry picked from commit ac4431e) Change-Id: Ifbf5fbfc2e27122362a2aaea4b62c7cf3ca46b1a

cole-h reviewed Nov 25, 2022

View reviewed changes

src/libexpr/eval.cc Outdated Show resolved Hide resolved

src/libexpr/primops.cc Outdated Show resolved Hide resolved

thufschmitt mentioned this pull request Nov 25, 2022

Don't create zero-lengh arrays in the primops #7315

Closed

thufschmitt assigned edolstra Dec 9, 2022

fricklerhandwerk added the contributor-experience Developer experience for Nix contributors label Mar 3, 2023

Théophane Hufschmitt and others added 3 commits November 16, 2023 12:27

Remove all the occurences of VLAs

ba3cb4a

There's generally no strict reason for using them, and they are somewhat fishy, so let's avoid them.

libexpr: Check primop arity earlier

0daccb1

roberth force-pushed the dont-use-vlas branch from df95344 to bdefeb5 Compare November 16, 2023 11:29

roberth requested a review from edolstra as a code owner November 16, 2023 11:29

github-actions bot added the with-tests Issues related to testing. PRs with tests have some priority label Nov 16, 2023

roberth force-pushed the dont-use-vlas branch from 78fc6b6 to 41b945a Compare November 16, 2023 12:24

roberth added the bug label Nov 16, 2023

roberth mentioned this pull request Nov 16, 2023

lib.lists.ifilter0: init NixOS/nixpkgs#214021

Merged

2 tasks

thufschmitt commented Nov 16, 2023

View reviewed changes

src/libexpr/eval.cc Outdated Show resolved Hide resolved

src/libexpr/eval.hh Outdated Show resolved Hide resolved

roberth added 8 commits November 16, 2023 15:38

maxPrimOpArity: 64 -> 8

12c91a8

This makes stack usage significantly more compact, allowing larger amounts of data to be processed on the same stack. PrimOp functions with more than 8 positional (curried) arguments should use an attrset instead.

readProcLink: Replace unnecessary value judgement by actual info

9fa133d

builtins.{any,all}: Use constant errorCtx

206ece0

Clang warned that the expanded code used to have a buffer overflow. Very strange, but also very avoidable.

ExprCall::eval: Heap allocate at arity 5+

91114a6

primops: Name stack reservation limits

1b9813e

removeAttrs: increase stack reservation to 64

a96be29

libexpr: Reduce nonRecursiveStackReservation

4e27f19

128 is still beyond the point where the allocation overhead is insignificant, but we don't anticipate to overflow for these use cases, so it's fine.

roberth force-pushed the dont-use-vlas branch from 41b945a to 4e27f19 Compare November 16, 2023 14:38

thufschmitt merged commit ac4431e into NixOS:master Nov 16, 2023

roberth mentioned this pull request Nov 17, 2023

Fix buildNoGc #9374

Merged

edolstra mentioned this pull request Nov 20, 2023

Revert use of boost::container::small_vector in the evaluator #9399

Merged

tebowy pushed a commit to tebowy/nix that referenced this pull request Jul 11, 2024

Merge pull request NixOS#7348 from thufschmitt/dont-use-vlas

5e18223

Remove the usage of VLAs in the code (cherry picked from commit ac4431e) Change-Id: Ifbf5fbfc2e27122362a2aaea4b62c7cf3ca46b1a

Uh oh!

Conversation

thufschmitt commented Nov 25, 2022 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

Uh oh!

Uh oh!

edolstra commented Nov 25, 2022

Uh oh!

nixos-discourse commented Dec 12, 2022

Uh oh!

tomberek commented Dec 19, 2022

Uh oh!

fricklerhandwerk commented Dec 19, 2022

Uh oh!

nixos-discourse commented Dec 19, 2022

Uh oh!

roberth commented Nov 16, 2023

Uh oh!

roberth commented Nov 16, 2023

Uh oh!

thufschmitt left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

roberth commented Nov 16, 2023

Uh oh!

thufschmitt commented Nov 16, 2023

Uh oh!

edolstra commented Nov 17, 2023

Uh oh!

roberth commented Nov 17, 2023

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

7 participants

thufschmitt commented Nov 25, 2022 •

edited

Loading