Jump to content

Recommended Posts

Posted

Como existe algum (muito... ou mesmo total) desconhecimento acerca desta biblioteca, decidi fazer um "pequeno" post acerca deste tópico.

Em primeiro lugar, esta biblioteca não depende do Objective-C. Pode ser utilizada em C puro. No entanto, a demonstração que vou fazer, vou fazê-la em Objective-C, pois é mais simples de exemplificar uma situação de concorrência.

Em segundo lugar, para poderem utilizar a biblioteca necessitam de um compilador moderno, como o Clang, que suporte para blocks. Blocks são uma extensão à linguagem C que pode ser equiparada à possibilidade de criar closures ou funções anónimas com retenção das variáveis do scope onde a função é criada.

Em terceiro lugar, vou utilizar Automatic Reference Counting, pelo que não farei qualquer gestão de memória de objectos. Esta funcionalidade pode encontrar-se igualmente no Clang.

O exemplo é simples. Tenho uma classe que tem um array mutável, e dois métodos acessores:

- Um acessor para o array sem qualquer tipo de protecção

- Um acessor assíncrono e exclusivo para o array (que deverão perceber após a visualização do código)

Aquilo que vou mostrar é como é possível fazer escritas concorrentes num objecto sem a necessidade de locks, utilizando uma pattern denominada Lockless Exclusive Accessor. Para tal, vou criar um grupo de threads utilizando a libdispatch que irão utilizar os métodos acessores para realizarem escritas no objecto e ver os resultados.

Para demonstrar a utilidade da biblioteca, vou "apenas" criar 1000 "threads" que irão realizar escritas concorrentes no array, deixando que a libdispatch faça a gestão de recursos que seja necessária.

Segue-se o código da classe que contém o array e os respectivos acessores:

#import <Foundation/Foundation.h>
#import <dispatch/dispatch.h>

typedef void(^ArrayAccessBlock)(NSMutableArray *array);

@interface DataObject : NSObject {
   NSMutableArray *array;
   dispatch_queue_t serialQueue;
}

- (void) asyncArrayAccessor:(ArrayAccessBlock)block;
- (void) unprotectedArrayAccessor:(ArrayAccessBlock)block;

@end

@implementation DataObject

- (id) init {
   self = [super init];

   if (self) {
       array = [NSMutableArray new];
       serialQueue = dispatch_queue_create("my serial queue", NULL);
   }

   return self;
}

- (void) unprotectedArrayAccessor:(ArrayAccessBlock)block {
   block(array);
}

- (void) asyncArrayAccessor:(ArrayAccessBlock)block {
   dispatch_async(serialQueue, ^{
       block(array);
   });
}

@end

E o código que realiza as escritas concorrentes e a apresentação de resultados:

#import <Foundation/Foundation.h>
#import <dispatch/dispatch.h>
#import "DataObject.h"

#define kConcurrentThreads  1000
#define kAmountOfInsertions 1000000
#define kPrintSeqArrayElems 20

int main(int argc, const char * argv[])
{
   NSLog(@"Program starting");

   int insertionsPerThread = kAmountOfInsertions / kConcurrentThreads;

   DataObject *dataObject = [DataObject new];

   dispatch_group_t dispatchGroup = dispatch_group_create();
   dispatch_queue_t concurrentQueue = dispatch_queue_create("my concurrent queue", DISPATCH_QUEUE_CONCURRENT);

   for (int i = 0; i < kConcurrentThreads; i++) {
       __block int h = i;

       dispatch_group_async(dispatchGroup, concurrentQueue, ^{
           for (int j = 0; j < insertionsPerThread; j++) {
               //[dataObject unprotectedArrayAccessor:^(NSMutableArray *array) {
               [dataObject asyncArrayAccessor:^(NSMutableArray *array) {
                   [array addObject:[NSString stringWithFormat:@"Thread #%d - iteration #%d", h, j]];
               }];
           }
       });
   }

   NSLog(@"ASYNC accessors are all working");

   dispatch_group_wait(dispatchGroup, DISPATCH_TIME_FOREVER);

   NSLog(@"ASYNC accessors have finished working");

   [dataObject syncArrayAccessor:^(NSMutableArray *array) {
       NSLog(@"Final SYNC accessor started");

       int r = arc4random() % (kAmountOfInsertions - kPrintSeqArrayElems - 1);

       NSLog(@"------------------ SAMPLE [%d - %d] ------------------", r, r + kPrintSeqArrayElems - 1);

       for (int i = 0; i < kPrintSeqArrayElems; i++) {
           NSLog(@"%@", array[r+i]);
       }

       NSLog(@"------------------- END OF SAMPLE -------------------");

       NSLog(@"Array contains %lu objects", (unsigned long)[array count]);
   }];

   return 0;
}

Se olharem para o código do DataObject, deverão perceber que contém uma serial queue, que é, no fundo, uma fila de operações que irá limitar o acesso ao array para que as escritas sejam feitas uma de cada vez, de forma exclusiva. Deverão também perceber que esse será o bottleneck do sistema, uma vez que as operações de escrita têm que esperar a sua vez para serem executadas.

E, se olharem para o main verão que vão ser imprimidas 4 mensagens em diferentes fases da execução, indicando quando todos os threads foram criados, quando todos os threads terminaram a sua execução e quando a execução do último acesso (de leitura) é feito ao objecto, imprimindo também uma amostra das inserções feitas no array.

Em primeiro lugar, alterando o código para utilizar o acessor não protegido, ficando:

        dispatch_group_async(dispatchGroup, concurrentQueue, ^{
           for (int j = 0; j < insertionsPerThread; j++) {
               [dataObject unprotectedArrayAccessor:^(NSMutableArray *array) {
               //[dataObject asyncArrayAccessor:^(NSMutableArray *array) {
                   [array addObject:[NSString stringWithFormat:@"Thread #%d - iteration #%d", h, j]];
               }];
           }
       });

O resultado obtido é:

2014-02-18 00:42:41.758 LEATest[654:303] Program starting
LEATest(654,0x102779000) malloc: *** error for object 0x1058004f0: pointer being freed was not allocated
*** set a breakpoint in malloc_error_break to debug
LEATest(654,0x1026f6000) malloc: *** error for object 0x1058004f8: incorrect checksum for freed object - object was probably modified after being freed.
*** set a breakpoint in malloc_error_break to debug

Como se pode perceber, não é boa ideia ter acessos concorrentes a um array. As escritas não são atómicas e, portanto, não é possível de ter concorrência sem qualquer tipo de protecção no objecto. A forma mais comum de implementar essa concorrência é através de locks ou mutexes. Neste caso não vou utilizar nenhum dos dois e vou deixar que o meu serial queue trate de gerir essa concorrência por mim.

Portanto, o resultado obtido utilizando o acessor protegido:

2014-02-18 01:45:38.277 LEATest[710:303] Program starting
2014-02-18 01:45:38.283 LEATest[710:303] ASYNC accessors are all working
2014-02-18 01:45:38.940 LEATest[710:303] ASYNC accessors have finished working
2014-02-18 01:45:41.692 LEATest[710:303] Final SYNC accessor started
2014-02-18 01:45:41.693 LEATest[710:303] ------------------ SAMPLE [84987 - 85006] ------------------
2014-02-18 01:45:41.693 LEATest[710:303] Thread #83 - iteration #831
2014-02-18 01:45:41.694 LEATest[710:303] Thread #87 - iteration #199
2014-02-18 01:45:41.694 LEATest[710:303] Thread #83 - iteration #832
2014-02-18 01:45:41.695 LEATest[710:303] Thread #87 - iteration #200
2014-02-18 01:45:41.695 LEATest[710:303] Thread #84 - iteration #372
2014-02-18 01:45:41.695 LEATest[710:303] Thread #83 - iteration #833
2014-02-18 01:45:41.696 LEATest[710:303] Thread #83 - iteration #834
2014-02-18 01:45:41.696 LEATest[710:303] Thread #84 - iteration #373
2014-02-18 01:45:41.697 LEATest[710:303] Thread #84 - iteration #374
2014-02-18 01:45:41.697 LEATest[710:303] Thread #85 - iteration #308
2014-02-18 01:45:41.697 LEATest[710:303] Thread #84 - iteration #375
2014-02-18 01:45:41.698 LEATest[710:303] Thread #85 - iteration #309
2014-02-18 01:45:41.698 LEATest[710:303] Thread #84 - iteration #376
2014-02-18 01:45:41.698 LEATest[710:303] Thread #87 - iteration #201
2014-02-18 01:45:41.699 LEATest[710:303] Thread #84 - iteration #377
2014-02-18 01:45:41.699 LEATest[710:303] Thread #87 - iteration #202
2014-02-18 01:45:41.700 LEATest[710:303] Thread #85 - iteration #310
2014-02-18 01:45:41.700 LEATest[710:303] Thread #87 - iteration #203
2014-02-18 01:45:41.700 LEATest[710:303] Thread #87 - iteration #204
2014-02-18 01:45:41.701 LEATest[710:303] Thread #87 - iteration #205
2014-02-18 01:45:41.701 LEATest[710:303] ------------------- END OF SAMPLE -------------------
2014-02-18 01:45:41.701 LEATest[710:303] Array contains 1000000 objects

Para poderem ter um pouco mais de contexto, o programa chegou a necessitar de cerca de 170MB de RAM durante a execução e a máquina onde foi executado tem 4 unidades de processamento com HyperThreading.

Há duas coisas que pretendo que extraiam deste resultado:

1. Foram precisos 6 milissegundos para conseguirmos criar 1000 threads com o libdispatch.

2. Pela amostra podemos verificar que existiu concorrência devido à não-sequencialidade das inserções.

Se já tiverem experiência com programação concorrente, vão perceber que, em primeiro lugar, é ridiculamente lento criar e manter 1000 threads em funcionamento para o mesmo processo. A latência da criação e destruição desse número de threads e a gestão de locks para impedir escritas simultâneas não atómicas seria maior do que o tempo de execução de todo este programa recorrendo a libdispatch.

É óbvio que é ridículo e nem a libdispatch está a criar 1000 threads reais. Durante toda a execução existiram, no máximo, 11 threads em funcionamento (4 quando ficou apenas o serialQueue em funcionamento). A biblioteca tratou de distribuir a carga pelos recursos de hardware existentes (e daí a indicação que é um queue concorrente - DISPATCH_QUEUE_CONCURRENT). Os novos threads que entraram em funcionamento tiveram que esperar que houvessem recursos para serem executados.

E a lógica por detrás do 11 é simples. A libdispatch cria 3 threads concorrentes com diferentes prioridades que não foram utilizados durante a execução deste programa. Isto significa que exisitiram 8 threads a funcionar durante a execução concorrente, dois para cada core (devido à capacidade de HyperThreading do processador):

- 1 para o serialQueue

- 7 que foram sendo utilizados pelas threads concorrentes e pelo main

Mas, em lado nenhum do programa foi indicado qual o número máximo de threads que a libdispatch devia utilizar. Toda essa gestão foi feita pela libdispatch. Eu limitei-me a esticar a corda e despejar uma quantidade ridícula de chamadas ao acessor. E, como eu coloquei 1000, também poderia ter colocado 1000000, fazendo um acesso por cada chamada:

2014-02-18 01:57:31.042 LEATest[1629:303] Program starting
2014-02-18 01:57:33.349 LEATest[1629:303] ASYNC accessors are all working
2014-02-18 01:57:33.349 LEATest[1629:303] ASYNC accessors have finished working
2014-02-18 01:57:35.588 LEATest[1629:303] Final SYNC accessor started
2014-02-18 01:57:35.588 LEATest[1629:303] ------------------ SAMPLE [40754 - 40773] ------------------
2014-02-18 01:57:35.589 LEATest[1629:303] Thread #40752 - iteration #0
2014-02-18 01:57:35.589 LEATest[1629:303] Thread #40756 - iteration #0
2014-02-18 01:57:35.589 LEATest[1629:303] Thread #40757 - iteration #0
2014-02-18 01:57:35.590 LEATest[1629:303] Thread #40758 - iteration #0
2014-02-18 01:57:35.590 LEATest[1629:303] Thread #40759 - iteration #0
2014-02-18 01:57:35.591 LEATest[1629:303] Thread #40755 - iteration #0
2014-02-18 01:57:35.591 LEATest[1629:303] Thread #40761 - iteration #0
2014-02-18 01:57:35.591 LEATest[1629:303] Thread #40762 - iteration #0
2014-02-18 01:57:35.592 LEATest[1629:303] Thread #40763 - iteration #0
2014-02-18 01:57:35.592 LEATest[1629:303] Thread #40760 - iteration #0
2014-02-18 01:57:35.592 LEATest[1629:303] Thread #40764 - iteration #0
2014-02-18 01:57:35.593 LEATest[1629:303] Thread #40765 - iteration #0
2014-02-18 01:57:35.593 LEATest[1629:303] Thread #40767 - iteration #0
2014-02-18 01:57:35.594 LEATest[1629:303] Thread #40769 - iteration #0
2014-02-18 01:57:35.594 LEATest[1629:303] Thread #40770 - iteration #0
2014-02-18 01:57:35.594 LEATest[1629:303] Thread #40768 - iteration #0
2014-02-18 01:57:35.595 LEATest[1629:303] Thread #40771 - iteration #0
2014-02-18 01:57:35.595 LEATest[1629:303] Thread #40766 - iteration #0
2014-02-18 01:57:35.595 LEATest[1629:303] Thread #40773 - iteration #0
2014-02-18 01:57:35.596 LEATest[1629:303] Thread #40774 - iteration #0
2014-02-18 01:57:35.596 LEATest[1629:303] ------------------- END OF SAMPLE -------------------
2014-02-18 01:57:35.597 LEATest[1629:303] Array contains 1000000 objects

O impacto na performance não foi demasiado drástico. Houve um aumento de cerca de 40MB na utilização da memória devido à necessidade de haverem mais scopes concorrentes em espera que iam fazer apenas uma chamada ao acessor. É óbvio que não é a forma mais eficiente de fazer a distribuição da carga (até porque o bottleneck é e sempre será a escrita no array para um caso como este), mas visto que a intenção é apenas demonstrar a escalabilidade e facilidade de utilização da libdispatch, um exemplo aparentemente ridículo pode ser um exemplo perfeitamente adequado.

Como nota final, isto é apenas uma (muito) pequena parte da API. A biblioteca é open source, não é exclusiva aos sistemas operativos da Apple e não é, de forma alguma, um trabalho incompleto.

Questões, críticas e notas são bem vindas.

“There are two ways of constructing a software design: One way is to make it so simple that there are obviously no deficiencies, and the other way is to make it so complicated that there are no obvious deficiencies. The first method is far more difficult.”

-- Tony Hoare

Posted

Uma pequena dúvida:

Pode ser utilizada em C puro.
para poderem utilizar a biblioteca necessitam de um compilador moderno, como o Clang, que suporte para blocks

Ou seja, em C puro propriamente dito (standards-compliant), não podemos utilizar libdispatch, correcto?

De qualquer das formas, dado que não tenho grande experiência em programação concorrente, não posso comentar sobre o potencial da lib, mas tenho-a aqui guardada para quando começar a investigar essa área.

É sempre bom tomar conhecimento das alternativas (à pthreads, no meu caso).

Posted

Ou seja, em C puro propriamente dito (standards-compliant), não podemos utilizar libdispatch, correcto?

Não é obrigatório. Os blocks só tornam tudo muito mais simples. Todas as funções da libdispatch têm uma variante terminada em _f que, em vez de receber um block, recebem uma função.

A libdispatch funciona por cima das threads. Dito de outra forma, é um nível de abstracção acima. Se tiveres que trabalhar ao nível das threads vais ter que as gerir e garantir que não vais estar a sobrecarregar o sistema.

“There are two ways of constructing a software design: One way is to make it so simple that there are obviously no deficiencies, and the other way is to make it so complicated that there are no obvious deficiencies. The first method is far more difficult.”

-- Tony Hoare

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
×
×
  • Create New...

Important Information

By using this site you accept our Terms of Use and Privacy Policy. We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.