Associatividade em caches

Confesso pra vocês que, por alguns anos, fiz uma confusão dos diabos sobre o que significa termos como “4 way set associative“. Sempre pensei nisso como se uma linha de cache fosse dividida em 4 pedaços e estava totalmente errado. O “set” do termo deveria ter chamado minha atenção.

Caches são memórias estáticas (hoje em dia, a maioria, pelo menos, contidas dentro do processador) que são bem mais rápidas que as memórias dinâmicas que estão contidas no “pentes” de memória instalados na sua placa mãe. O processador usa esses caches para acelerar o acesso à memória (evitando o acesso direto!).

Os caches são divididos em linhas. Nos processadores x86, desde o Pentium 4, pelo menos, cada linha de cache tem 64 bytes de tamanho. Não é possível lidar com menos de uma linha por vez, no que concerne os caches. Se você pedir para ler um único byte da memória, uma linha inteira (64 bytes) será carregada para o cache. Se você pedir para escrever um único byte, uma linha inteira de cache será, eventualmente, despejada para a memória, todos os 64 bytes, de uma só vez.

Cada linha é identificada por uma “marca” (uma tag) que corresponde aos bits superiores do endereço de memória usado. Os 6 bits inferiores do endereço compõem o offset dentro de uma linha. O que o processador faz quando você tentar ler/escrever num endereço é carregar uma linha inteira para o cache (L1) e marcá-la como pertencendo ao range de endereços onde os 6 bits inferiores vão de 0 até 0x3F… Daí toda leitura e escrita é feita com o processador procurando pela tag no cache e, se encontrar, o dado é escrito ou lido na linha.

Tipicamente o cache L1 (que é o cache mais próximo do processador lógico e o que mais nos interessa) tem 64 KiB de tamanho (em alguns processadores, 128 KiB ou 256 KiB). Vou assumir aqui 128 KiB… Com 128 KiB e 64 bytes por linha temos um total possível de armazenamento de 2048 linhas com tags diferentes. Quando você acessa a memória, o processador percorre todas as 2048 entradas procurando por uma tag idêntica à fornecida no endereço linear. Se achar, o acesso é feito no cache, senão, a linha é “carregada” (do cache L2).

Onde entra a associatividade de conjunto (set associativity)? Para melhorar essa pesquisa da tag alguns caches juntam mais de uma linha num conjunto de linhas, ligados (associados) à mesma tag, Ao invés de termos tag+offset, agora temos tag+way+offset. Onde way é uma indicação (um “caminho”) de uma linha em um conjunto (set) de linhas associadas a uma tag. Daí, “4 way set associative” significa que uma tag, nesse tipo de associativivdae possui 2 bits que indicam o caminho (way) para uma das 4 linhas associadas a uma tag.

O cache L1 está ligado a um processsador lógico individual e é dividido em 2 “tipos”: L1I (cache de instruções) e L1D (cache de dados). O cache L1I, em muitos processadores Intel modernos, é 4 way set assiciative, o que significa que cada tag comporta 4 linhas adjacentes ou 256 bytes. Cada linha é lidada de forma individual, mas ao alocar espaço para uma tag no cache, 4 linhas sempre serão alocadas. O cache L1D, por outro lado, é 8 way set associative. Alocação de 8 linhas por tag ou 512 bytes.

O cache L2 também costuma ser 8 way set associative e o cache L3 geralmente é chamado de full associative (ou seja, não tem o campo binário way no endereço linear – 1 tag, 1 linha).

Note que, e vou frisar isso, não é porque o cache L1D é 8 way set associative teremos o preenchimento de 8 linhas sempre que tentarmos ler/escrever um dado que não tenha uma tag no cache L1D… Apenas UMA linha é lida… mas 8 são sempre reservadas. Isso diminui, no nosso cache L1D de 128 KiB, a quantidade de tags de 2048 para 256, embora ainda tenhamos 2048 linhas disponíveis no cache.

Deu para esclarecer o que é “associatividade de conjunto” em caches?

Usando OracleDB em C (Oracle Call Interface)

Para usar o banco de dados Oracle em programas em C ou C++ é necessário linká-los contra a Oracle Call Interface (OCI) ou a OCCI (para C++)  . A versão mais atual pode ser baixada, gratuitamente, aqui. Recomendo baixar apenas a versão Basic Light e o SQL*Plus (para testar duas queries e algumas configs). As bibliotecas são fornecidas em forma de shared objects e é necessário criar links simbólicos em /usr/local/lib/ e configurar o linker com ldconfig, depois desses links criados. Isso consta na página sobre a instalação dos pacotes. Suponhamos que você resolveu descompactar os pacotes em /usr/local/lib/oracle/instantclient. A primeira coisa a fazer é criar a variável de ambiente $ORACLE_HOME apontando para esse diretório:

# echo "ORACLE_HOME='/usr/local/lib/oracle/instantclient'"\
 >> /etc/environment

Ou coloque isso no profile do usuário ou em outro lugar qualquer onde a variável seja exportada para os demais processos.

Dando uma olhada no diretório você encontrará vários arquivos com extensão .so*:

# find $ORACLE_HOME/ -type f -name '*.so*'
/usr/local/lib/oracle/instantclient/libclntshcore.so.19.1
/usr/local/lib/oracle/instantclient/libocci.so.19.1
/usr/local/lib/oracle/instantclient/liboramysql19.so
/usr/local/lib/oracle/instantclient/libsqlplus.so
/usr/local/lib/oracle/instantclient/libclntsh.so.19.1
/usr/local/lib/oracle/instantclient/libsqlplusic.so
/usr/local/lib/oracle/instantclient/libociei.so
/usr/local/lib/oracle/instantclient/libnnz19.so
/usr/local/lib/oracle/instantclient/libocijdbc19.so
/usr/local/lib/oracle/instantclient/libmql1.so
/usr/local/lib/oracle/instantclient/libipc1.so

Claro, esses arquivos terão links simbólicos em /usr/local/lib/, assim que você criá-los. Para que seu código funcione, é necessário linká-lo contra libclntsh.so e libclntshcore.so, outras libs podem ser necessárias, de acordo com as funções que você usar.

Num programa, a OCI funciona com base em uma hierarquia de objetos. O primeiro deles, que deve ser instanciado, é o environment ou OCIEnv. Isso é feito com a função OCIEnvCreate():

OCIEnv *envp;

if ( OCIEnvCreate( &envp,
                   OCI_THREADED,  // existe outras opções.
                   NULL, NULL, NULL, NULL, // Deixa a OCI
                                           // lidar com o
                                           // gerenciamento
                                           // de memória.
                   // nenhum dado extra.
                   0, NULL ) != OCI_SUCCESS )
{ ... Trata erro aqui... }

Todos os demais objetos serão, de uma forma ou de outra, atrelados a esse ambiente.

O Oracle tem várias camadas. Daí temos que instanciar um “servidor”, um “serviço”, e uma “sessão”, antes de pensarmos em enviar comandos (statements). Ou existem funções especializadas para criar/obter os ponteiros desses objetos ou usamos a função genérica OCIHandleAlloc(). No caso do objeto servidor:

OCISrv *srvp;
OCIError *errp;

if ( OCIHandleAlloc( envp, 
                     &srvp, 
                     OCI_HTYPE_SERVER ) != OCI_SUCCESS )
{ ... Trata erro aqui ... }

if ( OCIHandleAlloc( envp, 
                     &errp,
                     OCI_HTYPE_ERROR ) != OCI_SUCCESS )
{ ... Trata erro aqui ... }

if ( OCIServerAttach( srvp, 
                      errp,

                      // string de conexão (o "serviço" no
                      // tnsnames.ora).
                      connstr, strlen( connstr ),
                      OCI_DEFAULT ) != OCI_SUCCESS )
{ ... Trata erro aqui ... }

Note que precisamos criar, também, um objeto de erro. Todos os erros repostados na OCI são colocados nesse objeto. O retorno das funções devolve o status da mesma (não o “erro”). OCI_SUCCESS (0) é apenas um deles.

Uma vez que temos o server “atachado” ao ambiente, temos que criar o objeto de serviço. É ele quem conecta ao banco:

OCISvc *svcp;

if ( OCILogon2( envp, errp, &svcp,
                user, strlen( user ),
                password, strlen( password ),
                dbname, strlen( dbname ),
                OCI_DEFAULT ) != OCI_SUCCESS )
{ ... trata erro aqui... }

Note que o nome do banco é diferente do nome do serviço, anteriormente citado ao atacharmos o servidor. E a função OCILogon2() cria a instância do serviço, atrelada am ambiente, para nós. Não é necesário o uso de OCIHandleAlloc().

Nesse ponto, se tudo correu bem, já podemos enviar comandos para o banco de dados. E, surpresa das surpresas, isso é feito através de um outro objeto: OCIStmt, mas esse depende de outros objetos (OCIDescriptor e OCIBind, por exemplo). E, dependendo do tipo do campo contido no comando, teremos que usar ainda outros objetos, como o OCILobLocator, por exemplo, para o caso de queremos mexer com BLOBs.

Os objetos OCIDescriptor descrevem cada campo de retorno do comando e os atrela a duas variáveis: A que receberá o valor do tipo correspondente e um “indicador”. Esse indicador nos dirá se o campo é NULL, por exemplo. Isso tem que ser assim porque os tipos primimitivos de C não suportam NULL (a não ser que seja um ponteiro). Assim, a Oracle preferiu informar o estado do campo através desse “indicador”, à parte. Um exemplo simples. Suponha que queiramos executar um “SELECT 1 FROM DUAL” (comando comum para determinar se o banco está respondendo ou enviar “keep alives” para a sessão). Podemos fazer assim:

OCIStmt *stmtp;
OCIDefine *defp;
int value;
short int value_ind;
static const char sql[] = "select 1 "
                            "from dual";

// Prepara o comando.
if ( OCIStmtPrepare2( svcp,
                      &stmtp,
                      errp,
                      sql, sizeof sql - 1,
                      NULL, NULL,
                      OCI_NTV_SYNTAX ) != OCI_SUCCESS )
{ ... trata erro... }

// Define o retorno.
if ( OCIDefineByPos( stmtp,
                     &defp,
                     errp,
                     0,   // começa em 0.
                     &value, sizeof( value ),
                     SQLT_INT,
                     &value_ind,
                     NULL, NULL,
                     OCI_DEFAULT ) != OCI_SUCCESS )
{ ... trata erro aqui ... }

// Executa o comando.
if ( OCIStmtExecute( svcp,
                     stmtp,
                     errp,
                     0, 0, NULL, NULL,
                     OCI_DEFAULT ) != OCI_SUCCESS )
{ ... trata erro... }

printf( "$d\n", value );

// Libera o statement... Não precisaremos liberar defp
// porque ele está atrelado ao statement.
if ( OCIStmtRelease( stmtp, errp, 
                     NULL, 0, 
                     OCI_DEFAULT ) != OCI_SUCCESS )
{ ... trata erro aqui... }

Aqui não fiz questão de testar o indicador por um valor NULL no campo porque a ordem foi devolver 1.

É bom notar que a execução precisa de uma séria de parâmetros dependente do tipo de comando enviado ao banco de dados. Por exemplo, o primeiro 0 (zero) da sequência 0, 0, NULL, NULL à partir do 4º argumento de OCIStmtExecute nos diz quantas linhas deversão ser afetadas. Para “SELECTs” ele pode ser 0. Consulte a documentação da OCI.

Outra possibilidade é usarmos queries parametrizadas. Isso é feito colocando “variáveis” precedidas por : na query. Existem dois tipos, as nomeadas e as numeradas. Por exemplo: “SELECT * FROM ID=:id“. Aqui, retiramos o : do :id e usamos esse nome de parâmetro para criar objetos do tipo OCIBind, mais ou menos do mesmo jeito que fizemos com OCIDefine. Mas existem duas funções: OCIBindByPos() e OCIBindByName(). A função OCIBindByPos() funciona igualzinha a OCIDefineByPos(), onde criamos vários objetos começanco do índice 0. Mas, há um problema… Se o parâmetro for repetido no comando, qual “posição” usar? A primeira encontradda, mas para evitar essa ambiguidade, usamos OCIBindByName(), onde ao invés do índice, informamos o nome do parâmetro.

Antes de chamar OCIStmtExecute() as variáveis dos binds e seus indicadores devem ser inicializados e voilà!

Esse é o básico do uso da OCI. A documentação é extensa, cobrindo tópicos mais avançados como transações, connection pooling, etc… O documento tem mais de 1500 páginas e pode ser encontrado aqui.

PS: Para obter a próxima linha de um resultado, caso o SELECT devolva mais de uma, use a função OCIStmtFetch2().

Um contador mais “preciso”?

Vocês já viram meu contador de ciclos do homem pobre antes. Mas os processadores Intel/AMD têm dentro de si, desde o antigo Pentium, contadores de perforamnce bem mais precisos. O problema é que para lidar com eles temos que executar instruções que só estão disponíveis para o kernel (no ring 0). Como fazer?

Bem… O kernel disponibiliza uma syscall chamada perf_event_open() que nos dá, justamente, acesso aos performance counters de qualquer arquitetura de processadores que os implementem. Agora, o problema é que para usá-los precisamos obter um descritor de arquivo e usar syscalls como ioctl() e read(), E isso adicionaria overhead à medição, se a própria syscall perf_event_open não permitisse excluir esses ciclos extras. Consultando a documentação da syscall nas manpages, vemos que os membros exclude_kernel e exclude_hv, da estrutura da qual passamos o ponteiro, excluem da contagem final os ciclos gastos pelo kernel e hypervisor, respectivamente (se você estiver usando o código numa VM!).

Outra coisa é que perf_event_open não tem um wrapper ou protótipo em header files, então temos que chamar a syscall diretamente, seja usando o wrapper syscall(), seja em assembly. Eis o exemplo, pouco modificado, que acompanha a manpage:

/*
    perf.c

    Compilar com:
      cc -O2 -mtune=native -march=native -o perf perf.c
 */
#include <stdlib.h>
#include <stdio.h>
#include <unistd.h>
#include <sys/ioctl.h>
#include <linux/perf_event.h>
#include <asm/unistd.h>

// Necessária porque não há implementação dessa syscall
// na glibc.
static int perf_event_open( struct perf_event_attr *hw_event, 
                            pid_t pid,
                            int cpu, 
                            int group_fd, 
                            unsigned long flags )
{
  int r;
  register long g asm ("r10") = group_fd;
  register long f asm ("r8") = flags;

  __asm__ __volatile__ (
    "syscall"
      : "=a" (r) 
      : "a" (__NR_perf_event_open),
        "D" (hw_event),
        "S" (pid),
        "d" (cpu),
        "r" (g),
        "r" (f)
      : "memory" );

  return r;
}

int main( int argc, char **argv )
{
  unsigned long count;
  int fd;
  struct perf_event_attr pe = { 
    .type = PERF_TYPE_HARDWARE,
    .size = sizeof pe,
    .config = PERF_COUNT_HW_CPU_CYCLES,
    .disabled = 1,       // disabilita PMC.
    .exclude_kernel = 1, // exclui kernel.
    .exclude_hv = 1 };   // exclui hypervisor.

  // Infelizmente só pode rodar como root.
  if ( getuid() )
  {
    fputs( "ERROR: Need root priviledge.\n", stderr );
    return EXIT_FAILURE;
  }

  // Obtém o file descriptor, veja descrição
  // dos argumentos na manpage.
  if ( ( fd = perf_event_open( &pe, 0, -1, -1, 0 ) ) < 0 )
  {
    fputs( "Error opening PMC.\n", stderr );
    return EXIT_FAILURE;
  }

  // Reset e habilita o performance counter.
  ioctl( fd, PERF_EVENT_IOC_RESET, 0 );
  ioctl( fd, PERF_EVENT_IOC_ENABLE, 0 );

  // Rotina sendo medida.
  puts( "Measuring instruction count for this puts()." );

  // Desabilita, lê o performance counter 
  // e fecha o descritor.
  ioctl( fd, PERF_EVENT_IOC_DISABLE, 0 );
  read( fd, &count, sizeof count );
  close( fd );

  printf( "Used %lu cpu cycles.\n", count );

  return EXIT_SUCCESS;
}

Pra que você ainda usa ordenação de arrays?

Outro ponto interessante é que ordenar arrays pode ser uma coisa custosa, se feita depois que os preenche. Vale mais à pena preenchê-los já ordenados e existem algumas técnicas para isso. Eis a primeira, mais simples e menos eficiente: Abrir espaço para um “novo” elemento no array, copiando todos os elementos que o sucedem:

/* insert.c */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <inttypes.h>
#include "cycle_counting.h"

#define ELEMENTS 4096

// Insere v no array p de tamanho máximo max_size com
// quantidade conhecida de "elementos".
// Retorna a posição inserida ou -1 se não puder.
ssize_t insert( int *p, size_t max_size, size_t *elements, int v )
{
  int *lastp, *q;
  ssize_t pos;

  // Caso especial, se o número de elementos no array é
  // igual ou superior ao tanho máximo, não temos mais espaço.
  if ( *elements >= max_size )
    return -1;

  // Caso especial: Array vazio.
  if ( ! *elements )
  {
    *p = v;
    (*elements)++;

    return 0;
  }

  q = p;
  lastp = p + *elements - 1;
  pos = 0;
  while ( q <= lastp )
  {
    // procura pelo elemento com valor maior que v.
    if ( *q > v )
    {
      // Achou. Abre espaço.
      memmove( q + 1, q, (*elements - pos) * sizeof v );
      
      // Atribui o novo valor na posição corrente.
      *q = v;
      (*elements)++;

      return pos;
    }

    pos++, q++;
  }

  // Se não achou, insere no último elemento.
  *--q = v;
  (*elements)++;

  return --pos;
}

int main( void )
{
  size_t i;
  static int a[ELEMENTS];
  size_t elements = 0;
  counter_T c;

  c = BEGIN_TSC();
  for ( i = 0; i < ELEMENTS; i++ )
    if ( insert( a, ELEMENTS, &elements, rand() ) < 0 )
    {
      fputs( "ERROR inserting.\n", stderr );
      return EXIT_FAILURE;
    }
  END_TSC(&c);

  printf( "insert (inserindo %u elementos): %" PRIu64 " ciclos.\n", ELEMENTS, c );

  return EXIT_SUCCESS;
}

A função insert() aqui insere um valor v na posição correta, assim o array já estará ordenado depois de vários inserts. Note a chamada à função memmove(). Ela foi usada para evitar overlapping na cópia do buffer. O problema aqui é que, em cada inserção temos que procurar pelo item maior que o desejado (pos iterações) e depois mover os elementos finais uma “casa” para diante (elementos menos pos “elementos”). Podemos fazer melhor…

Se você abandonar o conceito de arrays e começar a trabalhar com árvores binárias (de preferência balanceradas), a velocidade aumenta um bocado porque a procura pela posição onde encaixar o valor é, no poior caso O(log_2(n)) e a inserção é, praticamente, O(1) (exceto pelo rebalanceamento da árvore, que é bem rápido. Eis a mesma rotina, acima, usando a libavl e árvores AVL:

/* avl.h */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <inttypes.h>
#include <avl.h>
#include "cycle_counting.h"

#define ELEMENTS 4096

static int cmp( const void *ap, const void *bp )
{
  const int *a, *b;

  a = ap; b = bp;
  return (*a > *b) - (*a < *b);
}

int main( void )
{
  // OBS: Usei um array para evitar alocações dinâmicas,
  //      além dos nós da árvore.
  avl_tree_t *treep;
  static int a[ELEMENTS];
  size_t i;

  counter_T c;

  if ( ! ( treep = avl_alloc_tree( cmp, NULL ) ) )
  {
    perror("avl_alloc_tree" );
    return EXIT_FAILURE;
  }

  c = BEGIN_TSC();
  for ( i = 0; i < ELEMENTS; i++ )
  {
    a[i] = rand();
    if ( ! avl_insert( treep, &a[i] ) )
    {
      fprintf( stderr, "ERROR inserting node %zu.\n", i );
      return EXIT_FAILURE;
    }
  }
  END_TSC(&c);

  avl_free_tree( treep );

  printf( "avl    (inserindo %u elementos): %" PRIu64 " ciclos.\n", ELEMENTS, c );

  return EXIT_SUCCESS;
}

Para compilar:

$ cc -O2 -o insert insert.c
$ cc -O2 -o avl avl.c -lavl

E medindo temos:

insert (inserindo 4096 elementos): 23435497 ciclos.
avl    (inserindo 4096 elementos): 5898354 ciclos.

Ou seja… 4 vezes mais rápido! Ahhh… instale o pacote libavl-dev antes.

As pesquisas, é claro, sempre são executadas com performance O(log_2(n)), no pior caso.

A desvantagem, além do aumento de complexidade, é que cada nó da árvore contém dados adicionais, além do desejado (ponteiro para nós à esquerda, à direita, 2 bits para o contador do AVL, etc)… Ainda, no caso da libavl temos que tomar cuidado para não inserirmos itens que já existam na árvore (existem outras funções além de avl_insert() para isso)..

Por que você ainda usa selection ou bubble sorting?

Já fazem 60 anos que um algoritmo melhor foi criado e ainda tem gente que usa selection ou bubble sorting. O quicksort, criado em 1960, na Russia, além de já constar da biblioteca padrão de C, é muito mais rápidos que seus antigos primos: Todos os 3 têm performance, no pior caso, de O(n^2), mas só o quicksort tem performance, no melhor caso, de O(n\cdot\log_2{n}). O “melhor” caso dos outros dois é o mesmo do pior caso, ou seja, O(n^2).

Isso cria uma diferença muito grande na ordenação de arrays muito grandes. Por exemplo, medidindo os ciclos das 3 rotinas contra um array de 65536 elementos, inteiros, “aleatórios”:

$ make run
Selection sort of 65536 elements: 16662073050 cycles (254243.06 cycles/element).
Bubble    sort of 65536 elements: 17845913475 cycles (272307.03 cycles/element).
Quicksort sort of 65536 elements: 19962414 cycles (304.60 cycles/element).

O famoso bubble sort, clássico, é cerca de 8% mais lento que o selection sort. Mas o quicksort é claramente superior, executando, neste caso, quase 1000 vezes mais rápido (um ganho de performance de 900% quase) que os outros dois.

Eis as rotinas:

# Makefile
#
# Depois de copiar isso, faça:
#   $ sed -i 's/^  /\t/' Makefile
#
# O wordpress "come" os tabstops, por isso
# fui obrigado a substituí-los por espaços.
#
CFLAGS=-O2 -mtune=native
LDFLAGS=-s
LDLIBS=

.PHONY: all clean distclean run

all: test_bubble test_selection test_qsort

test_bubble: test_bubble.o bubble.o
  $(CC) $(LDFLAGS) -o $@ $^ $(LDLIBS)

test_selection: test_selection.o selection.o
  $(CC) $(LDFLAGS) -o $@ $^ $(LDLIBS)

test_qsort: test_qsort.o
  $(CC) $(LDFLAGS) -o $@ $^ $(LDLIBS)

test_bubble.o: test_bubble.c common.h cycle_counting.h
test_selection.o: test_selection.c common.h cycle_counting.h
test_qsort.o: test_qsort.c cycle_counting.h
bubble.o: bubble.c common.h
selection.o: selection.c common.h

clean:
  -rm *.o

distclean: clean
  rm test_bubble test_selection test_qsort

run:
  @./test_selection
  @./test_bubble
  @./test_qsort

O header common.h só tem a definição “genérica” para a macro de swapping:

/* common.h */
#ifndef COMMON_H_INCLUDED_
#define COMMON_H_INCLUDED_

#define swap(a,b) \
  { typeof((a)) t; t = (a); (a) = (b); (b) = t; }

#endif

E as rotinas de selection e bubble sorting são essas:

/* selection.c */
#include <stddef.h>
#include "common.h"

/* A "seleção" é o primeiro elemento do array, que será
   comparado com todos os demais, havendo a troca apenas se
   o elemento selecionado for "maior que" qualquer um dos
   demais elementos. */
void selectionSort( int *buffp, size_t size )
{
  int *lastp, *p, *q;

  /* Precisamos saber quando parar, postanto, calculamos o
     ponteiro do último elemento válido do array. */
  lastp = buffp + size - 1;

  /* Loop externo. Começamos no primeiro e vamos até o
     penúltimo elemento do array. */
  p = buffp;
  while ( p < lastp )
  {
    /* Loop interno, vamos do próximo elemento do array,
       depois do selectionado, até o último. */
    q = p + 1;
    while ( q <= lastp )
    {
      // Comparamos o elemento apontado por p, o elemento
      // selectionado, com o apontado por q, um dos outros
      // elementos do array. Trocamos um pelo outro se
      // o elemento selecionado for maior que o outro.
      if ( *p > *q )
        swap( *p, *q );

      q++;
    }

    p++;
  }
}
/* bubble.c */
#include <stddef.h>
#include "common.h"

void bubbleSort( int *buffp, size_t size )
{
  int *lastp, *p;

  // Guarda o último elemento do array.
  lastp = buffp + size - 1;

  // Vai decrementnado o ponteiro do último elemento,
  // porque vamos levando o maior deles para o final.
  while ( lastp > buffp )
  {
    // Compara em pares, realizando as trocas, se
    // necessário, até os dois últimos elementos.
    p = buffp;
    while ( p < lastp )
    {
      if ( *p > *(p + 1) )
        swap( *p, *(p + 1) );

      p++;
    }

    lastp--;
  }
}

Como exemplo, eis a rotina de teste do selection sort. As outras duas não são muito diferentes…

/* test_selection.c */
#include <stdio.h>
#include <stdlib.h>
#include <inttypes.h>
#include "common.h"
#include "cycle_counting.h"

#define ELEMENTS 65536

extern void selectionSort( int *, size_t );

int main( void )
{
  counter_T c;
  int *buffp, *p;
  size_t n;

  // NO seed!

  buffp = malloc( ELEMENTS * sizeof *buffp );
  p = buffp;
  for ( n = 0; n < ELEMENTS; n++ )
    *p++ = rand();

  c = BEGIN_TSC();
  selectionSort( buffp, n );
  END_TSC(&c);

  free( buffp );

  printf( "Selection sort of %zu elements: "
          "%" PRIu64 " cycles (%.2f cycles/element).\n",
    n, c, c / (double)n );
}

A diferença entre test_selection.c e test_bubble.c é apenas a chamada da função. Já em test_qsort.c a seguinte rotina tem que ser adicionada:

static int cmp( const void *ap, const void *bp )
{
  const int *a, *b;

  a = ap; b = bp;
  return (*a > *b) - (*a < *b);
}

Bem como a ahamada ser modificada para:

qsort( buffp, n, sizeof *buffp, cmp );

As rotinas em cycle_counting.h são já velhas conhecidas do meu contador de ciclos do homem pobre.

Repare que não fiz nenhum seeding para obter os valores “aleatórios”, deixando que o LCG me desse a mesma sequência. Fiz isso para garantir que as medidas eram justas, nos 3 casos…

Uma simples chamada, na linha de comando ao make compila tudo…

Um argumento, errado, contra o quicksort é que ele é recursivo. Usa a pilha e para arrays muito grandes pode causar um stack overflow. Isso é impossível, visto que dada sua natureza de particionamentos binários recursivos, apenas 2\cdot log_2(n) níveis de empilhamento serão feitos. Ou seja, se, por exemplo, se tivermos um array de n=2^{32} elementos (um array gigantesco!), apenas usaremos uma pilha de 64 níveis. Ainda, existem meios de “derecursivizar” um algoritmo recursivo e é o que a libc faz.

Não recomendo: Usando funções da libc em códigos puramente em assembly

Sempre topo com essa questão em foruns e mídias como o Discord: Como usar funções da biblioteca padrão de C em códigos puramente escritos em assembly? É “fácil”, mas eu não recomendo. Primeiro mostrarei como, usando o NASM e o GCC e depois digo o por quê da não recomendação. Eis um “hello, world” simples:

; test.asm
; Compile com:
;   nasm -felf64 -o test.o test.asm

bits 64

; A glibc exige "RIP relative addressing". 
; De qualquer maneira, isso é sempre uma boa 
; prática no modo x86-64.
default rel

section .rodata

msg:
  db    `hello, world`,0

section .text

  ; Este símbolo está na glibc!
  extern puts

  global main
main:
  ; Chama puts(), passando o ponteiro da string.
  lea   rdi,[msg]
  call  puts wrt ..plt

  ; return 0;
  xor   eax,eax
  ret

O código acima é diretamente equivalente a:

#include <stdio.h>

int main( void )
{
  puts( "hello, world" );
  return 0;
}

Para compilar, linkar e testar:

$ nasm -felf64 -o test.o test.asm
$ gcc -o test test.o
$ ./test
hello, world

Simples assim. O gcc deve ser usado como linker porque ele sabe onde a libc está.

O wrt ..plt é um operador do NASM chamado With Referece To. Ele diz que o símbolo está localizado em uma section específica. No caso a section ..plt, que contém os saltos para as funções da libc (late binding). Isso é necessário, senão obterá um erro de linkagem porque o linker não encontrará o símbolo… PLT é a sigla de “Procedure Linkage Table“. É uma tabela com ponteiros para as funções carregadas dinamicamente da libc.

Eis o porque de minha não recomendação: O compilador nem sempre usa o nome “oficial” da função, que pode ser um #define num header e, ás vezes, existem argumentos adicionais “invisíveis” para certas funções “intrínsecas”, mas o principal argumento contra essa prática é que seu código não ficará menor ou mais rápido só porque você está usando assembly. Por exemplo, ambos os códigos em C e Assembly, acima, fazem exatamente a mesma coisa e têm o mesmíssimo tamanho final (6 KiB, extirpando os códigos de debbugging e stack protection, no caso de C).

De fato, é provável que você crie um código em assembly pior do que o compilador C criaria…

Addedum: Não recomendo, particularmente, que se tente escrever códigos em assembly que usem a libc no ambiente Windows. O problema é que Windows coloca algum código adicional nas funções. Por exemplo, A pilha deve ser alterada para acomodar SEH (Structured Exception Handling), no caso de main, é necessário chamar uma função chamada _main… Coisas assim são problemáticas para o novato.

Por que dimensionar vídeos com número par de linhas e colunas?

Já reparou nisso? Se você pede para dimensionar seus vídeos com número ímpar de linhas ou colunas o ffmpeg (e outros encoders) reclamam. Ainda, às vezes, quando você edita seu vídeo dimensionado dessa forma, ou observa colunas ou linhas pretas adicionadas no lado direito ou abaixo, ou linhas com “lixo” (um padrão de pixels maluco)… Isso acontece porque vídeos codificados com o padrão YUV 4:2:0 (ou NV12, por exemplo) ou qualquer um dos padrões YUV exigem que 4 pixels sejam agrupados juntos (2 pixels horizontais versus 2 pixels verticais) e, portanto, sua resolução tem que ter componentes pares.

Outro detalhe é relativo aos codecs. Se você usa um dos dois mais populares: h264 ou h265, cada quadro é dividido em blocos de pixels de tamanho (horizontal e vertical) múltiplos de 2^n (4×4, 8×8, 16×16 ou, no caso do h265, outros tamanhos múltiplos de 2^n). Isso significa, de novo, que a imagem precisa ter dimensionamento par nos dois sentidos.

Fica a dica…

O pesadelo dos “padrões” de tamanhos de vídeos

De novo esse troço? Well… Info para os aficionados por vídeos: Existem vários padrões de tamanho!

Os padrões mais simples de lembrar são os formatos widescreen, de aspecto \frac{16}{9}. Aqui temos o formato HD (1280×720), Full HD (1920×1080) e 4K (3840×2160). Vale notar que o formato 4K tem o dobro do tamanho (vertical e horizontal) do formato Full HD. Outra nota interessante é que ele não é, necessariamente “4K” (4 mil), mas tem 3840 pixels horizontais! Se bem que esses formatos geralmente são medidos pela quantidade de linhas, não de colunas. Seria esperado que o formato 4K fosse referenciado como 2.16K! :)

Existem padrões mais antigos também. O formato desses não seguem o aspecto \frac{16}{9}, mas são mais “quadrados”. Por exemplo, existe o padrão NTSC-M (720×486), resultando num formato de aspecto \frac{40}{27}, bem próximo do padrão letterbox de aspecto \frac{4}{3}. Por quê 486 linhas? No formato NTSC temos dois quadros entrelaçados de 262.5 linhas, ou 525 linhas por quadro completo, mas apenas 486 são visíveis, as 39 linhas “invisíveis” são usadas no pulso de retraço vertical… No entanto, existem formatos europeus (um deles usado no Brasil também): PAL-M e SECAM. O formato PAL-M usa as mesmas 525 linhas, mas tem 480 visíveis, resultando no formato 720×480 com um aspecto de \frac{3}{2}. É um aspecto um pouco mais “largo” (wide) que o letterbox. O padrão SECAM tem mais linhas que o NTSC-M e PAL-M (625 linhas), mas, até onde sei, não é mais usado.

Até aqui temos os formatos disponibilizados para TVs. No entanto, existem diversos formatos para vídeos em outras mídias, como cinema, por exemplo. Na telona o aspecto mais usado é de \frac{11}{8} e IMAX usa os aspectos de \frac{143}{10} ou \frac{19}{10}, dependendo do filme. Isso não significa que não existam outros aspectos em uso. Filmes chamados de “35 mm” costumam ter aspecto de \frac{3}{2}, ou seja, são duas vezes mais largos que a altura; “Super 16 mm”, por outro lado, usam \frac{5}{3}; Enquanto “70 mm” usam \frac{11}{5}; TVs antigas e alguns monitores tinham aspecto de \frac{5}{4}; Alguns distribuidores de filmes usam o aspecto de \frac{14}{9} para facilitar o escalonamento para os aspectos widescreen e letterbox; Alguns monitores atuais têm aspecto de \frac{8}{5}; O padrão norte-americano para a telona de cinema costuma seguir o aspecto de \frac{37}{2}… É um pesadelo, não? Não tenho como citar todas os “padrões” existentes porque simplesmente não tenho a acesso a todos eles. Não citei, por exemplo, o usado em “Super 8 mm” (popular nos primórdios, especialmente pela distribuição de filmes pornográficos nesse formato!).

Assim, recomendo que você se atenha aos padrões “de fato” mais comuns, como 540p (aspecto \frac{4}{3}); 720p, 1080p e 2160p (aspecto \frac{16}{9}) e use aquele esquema de colocar barras horizontais (ou verticais, se assim for necessário), centralizando o vídeo, se o mesmo não tiver o aspecto desejado.

Ahhh… ainda existe o pesadelo da velocidade de reprodução (quadros por segundo)… mas, deixarei isso pra depois…