KTachyon Posted February 18, 2014 at 02:24 AM Report #545637 Posted February 18, 2014 at 02:24 AM 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
pwseo Posted February 18, 2014 at 12:52 PM Report #545672 Posted February 18, 2014 at 12:52 PM 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).
KTachyon Posted February 18, 2014 at 02:18 PM Author Report #545677 Posted February 18, 2014 at 02:18 PM 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
Recommended Posts
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 accountSign in
Already have an account? Sign in here.
Sign In Now