Add Batched[A] type for efficient lazy addition #530
Merged
Conversation
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
This is the free semigroup -- it represents combining one or more elements using an associative operation. The values are stored in a tree structure, which can be traversed. If a semigroup for the underlying values becomes available, the structure can be summed to a single value. Batching represents a space/time trade-off (we use more space to use less time). In some cases these structures may become too big. To address this, there are constructors for Monoid[Batched[A]] and Semigroup[Batched[A]] instances that will periodically compact themselves (summing the tree to a single value) to keep the overall size below a specific parameter. Batched is appropriate anytime an eager concatenation or combination will produce intermediate values that will be thrown away, and a more efficient aggregate summation is possible. In those cases, building up a batch and then summing it should result in much more efficient operations. This commit adds the type, with documentation. It also adds some basic law-checks and tests.
This commit uses internal batching to avoid creating intermediate lists. We store a tree structure and then just render the list once at the end. There are probably other places that can benefit from the same approach, but this was one that was pointed out to me.x
| * `Batched[T]` values are guaranteed not to be empty -- that is, they | ||
| * will contain at least one `T` value. | ||
| */ | ||
| sealed abstract class Batched[T] { |
Collaborator
There was a problem hiding this comment.
can we extend Serializable?
There are a number of changes here: - Added Equiv[Batched[A]] (though it's slow) - Removed the non-compacting Monoid[Batched[A]] - Added/improved comments - Added .compact method - Ensured that folds are correctly compacted - Make Batched[A] serializable
| * One thing to note here is that two equivalent batches might | ||
| * produce different lists (for instance, if one of the batches has | ||
| * more zeros in it than another one). | ||
| */ |
Collaborator
There was a problem hiding this comment.
can we make this implicit?
Collaborator
|
👍 |
Collaborator
|
looks like a 2.10 compile failure: https://travis-ci.org/twitter/algebird/jobs/137652585#L1517 |
| */ | ||
| implicit def equiv[A](implicit s: Semigroup[A]): Equiv[Batched[A]] = | ||
| new Equiv[Batched[A]] { | ||
| def equiv(x: Batched[A], y: Batched[A]): Boolean = x.sum(s) == y.sum(s) |
Collaborator
There was a problem hiding this comment.
actually his needs Equiv[A] too. We should not be using universal equals inside here.
Collaborator
|
👍 when green |
Contributor
Author
|
Looks like a stalled build or something. 🚒 |
Collaborator
|
Thanks @non! this is great! |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
3 participants
Add this suggestion to a batch that can be applied as a single commit.
This suggestion is invalid because no changes were made to the code.
Suggestions cannot be applied while the pull request is closed.
Suggestions cannot be applied while viewing a subset of changes.
Only one suggestion per line can be applied in a batch.
Add this suggestion to a batch that can be applied as a single commit.
Applying suggestions on deleted lines is not supported.
You must change the existing code in this line in order to create a valid suggestion.
Outdated suggestions cannot be applied.
This suggestion has been applied or marked resolved.
Suggestions cannot be applied from pending reviews.
Suggestions cannot be applied on multi-line comments.
Suggestions cannot be applied while the pull request is queued to merge.
Suggestion cannot be applied right now. Please check back later.
This is the free semigroup -- it represents combining one or more
elements using an associative operation. The values are stored in a
tree structure, which can be traversed. If a semigroup for the
underlying values becomes available, the structure can be summed to a
single value.
Batching represents a space/time trade-off (we use more space to use
less time). In some cases these structures may become too big. To
address this, there are constructors for
Monoid[Batched[A]]andSemigroup[Batched[A]]instances that will periodically compactthemselves (summing the tree to a single value) to keep the overall
size below a specific parameter.
Batching is appropriate anytime an eager concatenation or combination
will produce expensive intermediate values that will be thrown away, and a more
efficient aggregate summation is possible. In those cases, building up
a batch and then summing it should result in much more efficient
operations.
This commit adds the type, with documentation. It also adds some basic
law-checks and tests.