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.

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

Speed up projections of structural records #7740

Merged
merged 3 commits into from
Oct 19, 2020
Merged

Speed up projections of structural records #7740

merged 3 commits into from
Oct 19, 2020

Conversation

hurryabit
Copy link
Contributor

@hurryabit hurryabit commented Oct 19, 2020 •
edited
Loading

Currently, for every projection of a structural record, we first do a
linear search through the field names to find the index of the field
value in the record value. Then we use this index to get the actual
value. However, since we started sorting the fields in alphabetic order
both in types and in values, this lookup will always yield the same
result for a fixed record type and a fixed field name, regardless of the
value of the record.

This PR changes the AST node for structural record projection to
contain the index of the field within the record as well. This
information is not contained in the DAML-LF archive itself and must
hence be filled in by the DAML-LF type checker.

The only context in which we use structural record prejections are
typeclass method invocations, which do a little bit more than just the
projection. Unfortunately, typeclass method invocations are the small
unit of work I can benchmark using the setup I have. In the end, they
are also the feature our users really care about.

My benchmarks show that the time a single typeclass method invocation
takes has dropped from ca. 210ns to ca. 130ns. That's a speedup of
ca. 1.6x.

CHANGELOG_BEGIN
[DAML Interpreter] Typeclass method invocation is now 1.6x faster.
CHANGELOG_END

Pull Request Checklist

  • Read and understand the contribution guidelines
  • Include appropriate tests
  • Set a descriptive title and thorough description
  • Add a reference to the issue this PR will solve, if appropriate
  • Include changelog additions in one or more commit message bodies between the CHANGELOG_BEGIN and CHANGELOG_END tags
  • Normal production system change, include purpose of change in description

NOTE: CI is not automatically run on non-members pull-requests for security
reasons. The reviewer will have to comment with /AzurePipelines run to
trigger the build.

This change is Reviewable

@hurryabit
Speed up projections of structural records
14f5062 
Currently, for every projection of a structural record, we first do a
linear search through the field names to find the index of the field
value in the record value. Then we use this index to get the actual
value. However, since we started sorting the fields in alphabetic order
both in types and in values, this lookup will always yield the same
result for a fixed record type and a fixed field name, regardless of the
value of the record.

This PR changes the AST node for structural record projection to
contain the index of the field within the record as well. This
information is not contained in the DAML-LF archive itself and must
hence be filled in by the DAML-LF type checker.

The only context in which we use structural record prejections are
typeclass method invocations, which do a little bit more than just the
projection. Unfortunately, typeclass method invocations are the small
unit of work I can benchmark using the setup I have. In the end, they
are also the feature our users really care about.

My benchmarks show that the time a single typeclass method invocation
takes has dropped from ca. 210ns to ca. 130ns. That's a speedup of
ca. 1.6x.

CHANGELOG_BEGIN
[DAML Interpreter] Typeclass method invocation is now 1.6x faster.
CHANGELOG_END
@hurryabit hurryabit changed the title WIP Speed up projections of structural records Speed up projections of structural records Oct 19, 2020
@hurryabit hurryabit marked this pull request as ready for review October 19, 2020 14:34
remyhaemmerle-da
remyhaemmerle-da approved these changes Oct 19, 2020
View reviewed changes
Copy link
Collaborator

@remyhaemmerle-da remyhaemmerle-da left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Not really fan of it, but I do not see other reasonable way to do it.

I any case, I would really like the new filed to be internalized as suggested in the PR.

Furthermore no reason to expose that outside the type checker/compiler

daml-lf/language/src/main/scala/com/digitalasset/daml/lf/language/Ast.scala Outdated Show resolved Hide resolved
daml-lf/interpreter/src/main/scala/com/digitalasset/daml/lf/speedy/Compiler.scala Outdated Show resolved Hide resolved
daml-lf/archive/src/main/scala/com/digitalasset/daml/lf/archive/DecodeV1.scala Outdated Show resolved Hide resolved
...idation/src/main/scala/com/digitalasset/daml/lf/validation/traversable/ExprTraversable.scala Outdated Show resolved Hide resolved
...idation/src/main/scala/com/digitalasset/daml/lf/validation/traversable/TypeTraversable.scala Outdated Show resolved Hide resolved
@hurryabit @remyhaemmerle-da
Apply Remy's suggestions
d52fa45 
Co-authored-by: Remy <remy.haemmerle@daml.com>
@hurryabit
Copy link
Contributor Author

FYI @nmarton-da

@hurryabit
Make it compile again
2c9ff02 
CHANGELOG_BEGIN
CHANGELOG_END
@hurryabit hurryabit merged commit 3665025 into master Oct 19, 2020
@hurryabit hurryabit deleted the faster-struct-projs branch October 19, 2020 20:05
martin-drhu-da pushed a commit that referenced this pull request Oct 19, 2020
@hurryabit
Speed up updates of structural records
b8edf45 
This is pretty much a verbatim copy of
#7740, but for updates of
structural records instead of projections.

This has no immediate performance impacts since the DAML compiler does
_currently_ not produce any structural record updates. Having both,
projections and updates, have the same runtime characteristics seems to
be a desirable property nevertheless, simply to avoid nasty surprises
should we ever start to use these updates.

Since the compiler does not produce any structural record updates, I
have no way to benchmark this. However, since the code is changed here
in the same way it was changed in the PR mentioned above, I expect the
same saving, which were roughly 80 ns per operation, where the previous
cost of an operation was _at most_ 210 ns.

CHANGELOG_BEGIN
CHANGELOG_END
@hurryabit hurryabit mentioned this pull request Oct 19, 2020
Merged
6 tasks
hurryabit added a commit that referenced this pull request Oct 20, 2020
@hurryabit
Speed up updates of structural records (#7742)
7b7839c 
This is pretty much a verbatim copy of
#7740, but for updates of
structural records instead of projections.

This has no immediate performance impacts since the DAML compiler does
_currently_ not produce any structural record updates. Having both,
projections and updates, have the same runtime characteristics seems to
be a desirable property nevertheless, simply to avoid nasty surprises
should we ever start to use these updates.

Since the compiler does not produce any structural record updates, I
have no way to benchmark this. However, since the code is changed here
in the same way it was changed in the PR mentioned above, I expect the
same saving, which were roughly 80 ns per operation, where the previous
cost of an operation was _at most_ 210 ns.

CHANGELOG_BEGIN
CHANGELOG_END
@remyhaemmerle-da remyhaemmerle-da mentioned this pull request Oct 20, 2020
Closed
6 tasks
remyhaemmerle-da added a commit that referenced this pull request Oct 22, 2020
@remyhaemmerle-da
Revert "Speed up projections of structural records (#7740)"
0295ec4 
This reverts commit 3665025.
remyhaemmerle-da added a commit that referenced this pull request Jan 11, 2022
@remyhaemmerle-da
LF: Revert #7742
7b53576 
Following #12338 which merges the two implementations of the
structural record projection introduced by #7740, this PR merges the two
implementations of the structural record introduced by #7742.

However, this PR does not try to cache the field index as it is done

1- unlike what it is suggested by commit message of #7742, the update
   has a linear complexity anyway, as it has to copy the whole struct.

2- the compiler does not produce any structural record updates

As result the PR is basically a revert of #7742.

CHANGELOG_BEGIN
CHANGELOG_END
@remyhaemmerle-da remyhaemmerle-da mentioned this pull request Jan 11, 2022
Merged
7 tasks
remyhaemmerle-da added a commit that referenced this pull request Jan 11, 2022
@remyhaemmerle-da
LF: Revert #7742 (#12354)
30300fd 
Following #12338 which merges the two implementations of the
structural record projection introduced by #7740, this PR merges the two
implementations of the structural record introduced by #7742.

However, this PR does not try to cache the field index as it is done

1- unlike what it is suggested by commit message of #7742, the update
   has a linear complexity anyway, as it has to copy the whole struct.

2- the compiler does not produce any structural record updates

As result the PR is basically a revert of #7742.

CHANGELOG_BEGIN
CHANGELOG_END
@akrmn akrmn mentioned this pull request Nov 14, 2023
Merged
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Reviewers

@remyhaemmerle-da remyhaemmerle-da remyhaemmerle-da 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.
2 participants
@hurryabit @remyhaemmerle-da