19 de junho de 2017 - Código

Lições de performances aprendidas com Roslyn

#1 - ObjectPool (... e PooledStringBuilder)

Quando pensamos sobre o código-fonte do Roslyn, deveríamos pensar em performance! Eu gostaria de compartilhar algumas técnicas de performance e práticas de codificação que tenho aprendido estudando Roslyn. Por isso resolvi blogar sobre o tema.

Vamos começar com o incrível ObjectPool. Trata-se do tipo que é usado pelo compilador para tratar de objetos reusados frequentemente que normalmente seriam instanciados e descartados rapidamente. Ele reduz a quantidade e o peso das coletas de lixo que vão ocorrer em runtime.


/// <summary>
/// Generic implementation of object pooling pattern with predefined pool size limit. The main
/// purpose is that limited number of frequently used objects can be kept in the pool for
/// further recycling.
/// 
/// Notes: 
/// 1) it is not the goal to keep all returned objects. Pool is not meant for storage. If there
///    is no space in the pool, extra returned objects will be dropped.
/// 
/// 2) it is implied that if object was obtained from a pool, the caller will return it back in
///    a relatively short time. Keeping checked out objects for long durations is ok, but 
///    reduces usefulness of pooling. Just new up your own.
/// 
/// Not returning objects to the pool in not detrimental to the pool's work, but is a bad practice. 
/// Rationale: 
///    If there is no intent for reusing the object, do not use pool - just use "new". 
/// </summary>

Bacana os comentários. Não é memso? Eu simplesmente adoro essa abordagem informal de comentar que realmente provê informação relevante sobre o que está ocorrendo.


internal class ObjectPool<T> where T : class
{
    [DebuggerDisplay("{Value,nq}")]
    private struct Element
    {
        internal T Value;
    }

    /// <remarks>
    /// Not using System.Func{T} because this file is linked into the (debugger) Formatter,
    /// which does not have that type (since it compiles against .NET 2.0).
    /// </remarks>
    internal delegate T Factory();

    // Storage for the pool objects. The first item is stored in a dedicated field because we
    // expect to be able to satisfy most requests from it.
    private T _firstItem;
    private readonly Element[] _items;

Sim! Roslyn envolve valores em uma struct para armazenar. A ideia aqui é evitar problema de performance quando estiverem sendo atribuídos valores para uma posição de um array. Não haverá necessidade de verificar em tempo de execução se o tipo do objeto é compatível (Lembrando que arrays são variant na CLR).


internal ObjectPool(Factory factory)
    : this(factory, Environment.ProcessorCount * 2)
{ }

internal ObjectPool(Factory factory, int size)
{
    Debug.Assert(size >= 1);
    _factory = factory;
    _items = new Element[size - 1];
}

private T CreateInstance()
{
    var inst = _factory();
    return inst;
}

ObjectPool é um tipo interno. Logo, é natural que realize validações leves. Por padrão, the Debug.Assert funciona apenas em debug. Não há impacto de validações em release.

/// <summary>
/// Produces an instance.
/// </summary>
/// <remarks>
/// Search strategy is a simple linear probing which is chosen for it cache-friendliness.
/// Note that Free will try to store recycled objects close to the start thus statistically 
/// reducing how far we will typically search.
/// </remarks>
internal T Allocate()
{
    // PERF: Examine the first element. If that fails, AllocateSlow will look at the remaining elements.
    // Note that the initial read is optimistically not synchronized. That is intentional. 
    // We will interlock only when we have a candidate. in a worst case we may miss some
    // recently returned objects. Not a big deal.
    T inst = _firstItem;
    if (inst == null || inst != Interlocked.CompareExchange(ref _firstItem, null, inst))
    {
        inst = AllocateSlow();
    }

    return inst;
}

private T AllocateSlow()
{
    var items = _items;

    for (int i = 0; i < items.Length; i++)
    {
        // Note that the initial read is optimistically not synchronized. That is intentional. 
        // We will interlock only when we have a candidate. in a worst case we may miss some
        // recently returned objects. Not a big deal.
        T inst = items[i].Value;
        if (inst != null)
        {
            if (inst == Interlocked.CompareExchange(ref items[i].Value, null, inst))
            {
                return inst;
            }
        }
    }

    return CreateInstance();
}

Trabalhar com valores armazenados diretamente em campos é mais rápido do que com arrays (não são necessárias variáveis de índice, por exemplo). Por causa disso, há um campo dedicado que deverá ser suficiente na maior parte do tempo.

Interlocked é postergado até o último momento responsável (quase o primeiro irresponsável).

/// <summary>
/// Returns objects to the pool.
/// </summary>

/// <remarks>
/// Search strategy is a simple linear probing which is chosen for it cache-friendliness.
/// Note that Free will try to store recycled objects close to the start thus statistically 
/// reducing how far we will typically search in Allocate.
/// </remarks>
internal void Free(T obj)
{
    Validate(obj);
    ForgetTrackedObject(obj);

    if (_firstItem == null)
    {
        // Intentionally not using interlocked here. 
        // In a worst case scenario two objects may be stored into same slot.
        // It is very unlikely to happen and will only mean that one of the objects will get collected.
        _firstItem = obj;
    }
    else
    {
        FreeSlow(obj);
    }
}

private void FreeSlow(T obj)
{
    var items = _items;
    for (int i = 0; i < items.Length; i++)
    {
        if (items[i].Value == null)
        {
            // Intentionally not using interlocked here. 
            // In a worst case scenario two objects may be stored into same slot.
            // It is very unlikely to happen and will only mean that one of the objects will get collected.
            items[i].Value = obj;
            break;
        }
    }
}

No retorno, não há verificações de concorrência. Se algum valor se perder, tudo bem! Como os comentários deixam claro, a perda de objetos é rara. Então, é mais barato criar novas instâncias se necessário do que tentar evitar acesso concorrente.

Perceba que o método Free vai armazenar todos os objetos reciclados logo no início do array – o que torna a alocação ainda mais rápida.

Usando!

ObjectPool é um conceito de baixo nível. Segue um caso de uso bastante interessante.


/// <summary>
/// The usage is:
///        var inst = PooledStringBuilder.GetInstance();
///        var sb = inst.builder;
///        ... Do Stuff...
///        ... sb.ToString() ...
///        inst.Free();
/// </summary>
internal class PooledStringBuilder
{
    public readonly StringBuilder Builder = new StringBuilder();
    private readonly ObjectPool<PooledStringBuilder> _pool;

    private PooledStringBuilder(ObjectPool<PooledStringBuilder> pool)
    {
        Debug.Assert(pool != null);
        _pool = pool;
    }

    public int Length
    {
        get { return this.Builder.Length; }
    }

    public void Free()
    {
        var builder = this.Builder;

        // do not store builders that are too large.
        if (builder.Capacity <= 1024)
        {
            builder.Clear();
            _pool.Free(this);
        }
        else
        {
            _pool.ForgetTrackedObject(this);
        }
    }

    [System.Obsolete("Consider calling ToStringAndFree instead.")]
    public new string ToString()
    {
        return this.Builder.ToString();
    }

    public string ToStringAndFree()
    {
        string result = this.Builder.ToString();
        this.Free();

        return result;
    }

    public string ToStringAndFree(int startIndex, int length)
    {
        string result = this.Builder.ToString(startIndex, length);
        this.Free();

        return result;
    }

    // global pool
    private static readonly ObjectPool<PooledStringBuilder> s_poolInstance = CreatePool();

    // if someone needs to create a private pool;
    /// <summary>
    /// If someone need to create a private pool
    /// </summary>
    /// <param name="size">The size of the pool.</param>
    /// <returns></returns>
    public static ObjectPool<PooledStringBuilder> CreatePool(int size = 32)
    {
        ObjectPool<PooledStringBuilder> pool = null;
        pool = new ObjectPool<PooledStringBuilder>(() => new PooledStringBuilder(pool), size);
        return pool;
    }

    public static PooledStringBuilder GetInstance()
    {
        var builder = s_poolInstance.Allocate();
        Debug.Assert(builder.Builder.Length == 0);
        return builder;
    }

    public static implicit operator StringBuilder(PooledStringBuilder obj)
    {
        return obj.Builder;
    }
}

Roslyn usa StringBuilder intensamente. Aqui, ObjectPool salva um bocado de trabalho criando novas instâncias e com o GC.

Era isso.

1 pensamento em “Lições de performances aprendidas com Roslyn”

  1. Elemar, quando você fala isso: “Trabalhar com valores armazenados diretamente em campos é mais rápido do que com arrays. Por causa disso, há um campo dedicado que deverá ser suficiente na maior parte do tempo.”

    Que dizer que ele ao invés de usar o field _items da classe, cria uma variável items e usa ela, e nesse caso o código executa mais rápido?

    O mesmo se repete com o “T inst = items[i].Value” ao invés de acessar sempre “items[i].Value” usar a variável fica mais rápido?

    Muito show o artigo, no aguardo dos próximos!!!

Deixe uma resposta

O seu endereço de e-mail não será publicado. Campos obrigatórios são marcados com *