[Bug] Improve token filtering logic

[pmaytak]

Which version of MSAL.NET are you using?
4.40.0

Actual behavior
In FindAccessTokenAsync and FilterWithLogging, inefficient Linq is used when filtering the token collection resulting in unnecessary List object allocation.

Possible solution
Main tasks:

• Replace IReadOnlyList with List in accessor and filtering methods.
• In FilterWithLogging, replace list = list.Where(predicate).ToList(); with list.RemoveAll(e => !predicate(e));
• Investigate if the same changes have to be made on other methods, like the refresh token filtering.
• (optional) Investigate using SegmentedList instead of List
• Run performance tests

Additional context / logs / screenshots / links to code
Context from conversation:

Notice there are 4+ branches, all from a single method. Here is the source code in MSAL library:

        IReadOnlyList<MsalAccessTokenCacheItem> tokenCacheItems = GetAllAccessTokensWithNoLocks(true, partitionKey);
        ...

        tokenCacheItems = FilterByHomeAccountTenantOrAssertion(requestParams, tokenCacheItems);
        tokenCacheItems = FilterByTokenType(requestParams, tokenCacheItems);
        tokenCacheItems = FilterByScopes(requestParams, tokenCacheItems);
        tokenCacheItems = await FilterByEnvironmentAsync(requestParams, tokenCacheItems).ConfigureAwait(false);

   internal static IReadOnlyList<T> FilterWithLogging<T>(
       this IReadOnlyList<T> list,
       Func<T, bool> predicate,
       ICoreLogger logger,
       string logPrefix)
    {
        if (logger.IsLoggingEnabled(LogLevel.Verbose))
        {
            logger.Verbose($"{logPrefix} - item count before: {list.Count} ");
        }

        list = list.Where(predicate).ToList();

        if (logger.IsLoggingEnabled(LogLevel.Verbose))
        {
            logger.Verbose($"{logPrefix} - item count after: {list.Count} ");
        }

        return list;
    }

What if you change the code to:

        List<MsalAccessTokenCacheItem> tokenCacheItems = GetAllAccessTokensWithNoLocks(true, partitionKey);

        requestParams.RequestContext.Logger.Always($"[FindAccessTokenAsync] Discovered {tokenCacheItems.Count} access tokens in cache using partition key: {partitionKey}");

        if (tokenCacheItems.Count == 0)
        {

            logger.Verbose("No access tokens found in the cache. Skipping filtering. ");
            requestParams.RequestContext.ApiEvent.CacheInfo = CacheRefreshReason.NoCachedAccessToken;

            if (AcquireTokenInLongRunningOboWasCalled(requestParams))
            {
                logger.Error("[FindAccessTokenAsync] AcquireTokenInLongRunningProcess was called and OBO token was not found in the cache.");
                throw new MsalClientException(MsalError.OboCacheKeyNotInCacheError, MsalErrorMessage.OboCacheKeyNotInCache);
            }

            return null;
        }

        FilterByHomeAccountTenantOrAssertion(requestParams, tokenCacheItems);
        FilterByTokenType(requestParams, tokenCacheItems);
        FilterByScopes(requestParams, tokenCacheItems);
        await FilterByEnvironmentAsync(requestParams, tokenCacheItems).ConfigureAwait(false);

With:

    internal static void FilterWithLogging<T>(
       this List<T> list,
       Func<T, bool> predicate,
       ICoreLogger logger,
       string logPrefix)
    {
        if (logger.IsLoggingEnabled(LogLevel.Verbose))
        {
            logger.Verbose($"{logPrefix} - item count before: {list.Count} ");
        }

        list.RemoveAll(e => !predicate(e));

        if (logger.IsLoggingEnabled(LogLevel.Verbose))
        {
            logger.Verbose($"{logPrefix} - item count after: {list.Count} ");
        }
    }

Now you just need a single list, with much reduced LOH allocations. The single list can either be reused or switched to use segmented list. So no LOH allocation is totally achievable.

Given that we’re doing multiple levels of filtering, it’s even possible to apply the most effective filter first, and/or combine them into a single stage filtering.

I said quite a few times that Linq.Enumerable is total disregard of proper data structure and algorithm design. The flip side of the story is you need precise selection/craftmanship in your data structure and algorithm design.