Skip to content
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.

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

stringToEnum: Sort enum fields before inline for #17527

Closed
squeek502 opened this issue Oct 15, 2023 · 1 comment
Closed

stringToEnum: Sort enum fields before inline for #17527

squeek502 opened this issue Oct 15, 2023 · 1 comment
Labels
contributor friendly This issue is limited in scope and/or knowledge of Zig internals. optimization standard library This issue involves writing Zig code for the standard library.

Comments

@squeek502
Copy link
Collaborator

squeek502 commented Oct 15, 2023

As discovered in Vexu/arocc#524 (Vexu/arocc#524 (comment)), stringToEnum could have considerably better codegen for large enums if it were sorted by field length before the inline for:

zig/lib/std/meta.zig

Lines 41 to 46 in a126afa

inline for (@typeInfo(T).Enum.fields) |enumField| {
if (mem.eql(u8, str, enumField.name)) {
return @field(T, enumField.name);
}
}
return null;

Here's a benchmark focusing on just different possible sorting of enum fields (this is with 3948 fields in the enum, shortest field length is 3 and longest is 43):

-------------------- unsorted ---------------------
            always found: 3718ns per lookup
not found (random bytes): 6638ns per lookup
 not found (1 char diff): 3819ns per lookup

----------- sorted by length (desc) ---------------
            always found: 1176ns per lookup
not found (random bytes): 68ns per lookup
 not found (1 char diff): 1173ns per lookup

----------- sorted by length (asc) ----------------
            always found: 1054ns per lookup
not found (random bytes): 67ns per lookup
 not found (1 char diff): 1053ns per lookup

-------- sorted lexicographically (asc) -----------
            always found: 2764ns per lookup
not found (random bytes): 4615ns per lookup
 not found (1 char diff): 2750ns per lookup

This would ultimately be a trade-off between compile time and runtime performance. I haven't tested to see how much of an impact on the compile time the comptime sorting of the fields would incur. We might end up hitting #4055, in which case this optimization might need to wait a bit.

Note: Sorting would also make it easy to create a fast path that checks that the str.len is within the bounds of the longest/shortest enum field.

cc @Validark

@squeek502 squeek502 added optimization standard library This issue involves writing Zig code for the standard library. labels Oct 15, 2023
@squeek502 squeek502 changed the title stringToEnum: Sort enum fields by length (longest to shortest) before inline for stringToEnum: Sort enum fields before inline for Oct 15, 2023
@squeek502 squeek502 added the contributor friendly This issue is limited in scope and/or knowledge of Zig internals. label Oct 15, 2023
@squeek502
Copy link
Collaborator Author

squeek502 commented Oct 15, 2023

Duplicate of #3863, moved this there instead

@squeek502 squeek502 closed this as not planned Won't fix, can't repro, duplicate, stale Oct 15, 2023
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
contributor friendly This issue is limited in scope and/or knowledge of Zig internals. optimization standard library This issue involves writing Zig code for the standard library.
Projects
None yet
Development

No branches or pull requests

1 participant