This is an automated email from the ASF dual-hosted git repository. btellier pushed a commit to branch master in repository https://gitbox.apache.org/repos/asf/james-project.git
commit 61523b2ef59b29e6e0d45d8f1a60324aaa03cebc Author: Benoit Tellier <[email protected]> AuthorDate: Mon May 17 07:50:07 2021 +0700 [PERFORMANCE] Mailboxes metadata: Avoid O(n2) algorithm to compute hasChildren 0.56% running an inefficient algorithm to state which mailboxes have kids, in O(n2). While the percentage is low acting on it with likely improve p99 for `Mailbox/get` with many mailboxes and is thus worth writing. --- .../james/mailbox/store/StoreMailboxManager.java | 33 ++++++++++++++-------- 1 file changed, 22 insertions(+), 11 deletions(-) diff --git a/mailbox/store/src/main/java/org/apache/james/mailbox/store/StoreMailboxManager.java b/mailbox/store/src/main/java/org/apache/james/mailbox/store/StoreMailboxManager.java index 5de99f6..89f6e0a 100644 --- a/mailbox/store/src/main/java/org/apache/james/mailbox/store/StoreMailboxManager.java +++ b/mailbox/store/src/main/java/org/apache/james/mailbox/store/StoreMailboxManager.java @@ -27,6 +27,7 @@ import java.time.Duration; import java.util.ArrayList; import java.util.EnumSet; import java.util.List; +import java.util.Map; import java.util.Optional; import java.util.Set; import java.util.function.Function; @@ -97,6 +98,7 @@ import com.google.common.base.Preconditions; import com.google.common.collect.ImmutableList; import com.google.common.collect.ImmutableSet; import com.google.common.collect.Iterables; +import com.google.common.collect.Lists; import reactor.core.publisher.Flux; import reactor.core.publisher.Mono; @@ -660,19 +662,33 @@ public class StoreMailboxManager implements MailboxManager { private Function<Flux<Mailbox>, Flux<MailboxMetaData>> withCounters(MailboxSession session, List<Mailbox> mailboxes) { MessageMapper messageMapper = mailboxSessionMapperFactory.getMessageMapper(session); + Map<MailboxPath, Boolean> parentMap = parentMap(mailboxes, session); int concurrency = 4; return mailboxFlux -> mailboxFlux .flatMap(mailbox -> retrieveCounters(messageMapper, mailbox, session) .map(Throwing.<MailboxCounters, MailboxMetaData>function( - counters -> toMailboxMetadata(session, mailboxes, mailbox, counters)) + counters -> toMailboxMetadata(session, parentMap, mailbox, counters)) .sneakyThrow()), concurrency); } + private Map<MailboxPath, Boolean> parentMap(List<Mailbox> mailboxes, MailboxSession session) { + return mailboxes.stream().map(Mailbox::generateAssociatedPath) + .flatMap(path -> { + List<MailboxPath> hierarchyLevels = path.getHierarchyLevels(session.getPathDelimiter()); + return Lists.reverse(hierarchyLevels).stream().skip(1); + }) + .collect(Guavate.toImmutableMap( + Function.identity(), + any -> true, + (a, b) -> true)); + } + private Function<Flux<Mailbox>, Flux<MailboxMetaData>> withoutCounters(MailboxSession session, List<Mailbox> mailboxes) { + Map<MailboxPath, Boolean> parentMap = parentMap(mailboxes, session); return mailboxFlux -> mailboxFlux .map(Throwing.<Mailbox, MailboxMetaData>function( - mailbox -> toMailboxMetadata(session, mailboxes, mailbox, MailboxCounters + mailbox -> toMailboxMetadata(session, parentMap, mailbox, MailboxCounters .builder() .mailboxId(mailbox.getMailboxId()) .count(0) @@ -738,30 +754,25 @@ public class StoreMailboxManager implements MailboxManager { .map(Mailbox::getMailboxId); } - private MailboxMetaData toMailboxMetadata(MailboxSession session, List<Mailbox> mailboxes, Mailbox mailbox, MailboxCounters counters) throws UnsupportedRightException { + private MailboxMetaData toMailboxMetadata(MailboxSession session, Map<MailboxPath, Boolean> parentMap, Mailbox mailbox, MailboxCounters counters) throws UnsupportedRightException { return new MailboxMetaData( mailbox.generateAssociatedPath(), mailbox.getMailboxId(), getDelimiter(), - computeChildren(session, mailboxes, mailbox), + computeChildren(parentMap, mailbox), Selectability.NONE, storeRightManager.getResolvedMailboxACL(mailbox, session), counters); } - private MailboxMetaData.Children computeChildren(MailboxSession session, List<Mailbox> potentialChildren, Mailbox mailbox) { - if (hasChildIn(mailbox, potentialChildren, session)) { + private MailboxMetaData.Children computeChildren(Map<MailboxPath, Boolean> parentMap, Mailbox mailbox) { + if (parentMap.getOrDefault(mailbox.generateAssociatedPath(), false)) { return MailboxMetaData.Children.HAS_CHILDREN; } else { return MailboxMetaData.Children.HAS_NO_CHILDREN; } } - private boolean hasChildIn(Mailbox parentMailbox, List<Mailbox> mailboxesWithPathLike, MailboxSession mailboxSession) { - return mailboxesWithPathLike.stream() - .anyMatch(mailbox -> mailbox.isChildOf(parentMailbox, mailboxSession)); - } - @Override public Flux<MessageId> search(MultimailboxesSearchQuery expression, MailboxSession session, long limit) throws MailboxException { return getInMailboxIds(expression, session) --------------------------------------------------------------------- To unsubscribe, e-mail: [email protected] For additional commands, e-mail: [email protected]
