Représentations des données

Le format arrow a des spécifications qui permettent aux différentes librairies de communiquer sans avoir à faire de conversion. Ce spécifications correspondent à des exigences de compatibilités et des propositions de fonctionnalités, mais nous allons vérifier ici quels formats de données sont utilisés par le package arrow et les comparer à ce qui est fait dans R.

Pour ce faire, nous allons inspecter les représentations utilisées par R à l’aide de fonctions C.

Vecteur booléen

Sous R

Un vecteur booléen dans R est, en interne, un vecteur d’entiers de taille 32 bits. Ce format n’est vraiment pas économe en taille. Nous gâchons 2^32 = 4 294 967 296 modalités possibles pour écrire des données qui n’utilisent que 3 modalités.

v <- c(TRUE, TRUE, NA, FALSE, FALSE, NA, TRUE, TRUE, TRUE)

library(inline)
code <- "
SEXP res = PROTECT(NEW_RAW(4));
uint32_t val = LOGICAL(x)[INTEGER(i)[0]];
memcpy(RAW(res), &val, 4);
UNPROTECT(1);
return res;
"
get_value <- cfunction(signature(x = "character", i = "integer"), code, includes = "#include <stdint.h>")

get_value(v, 0L)
[1] 01 00 00 00
get_value(v, 1L)
[1] 01 00 00 00
get_value(v, 2L)
[1] 00 00 00 80
get_value(v, 3L)
[1] 00 00 00 00
get_value(v, 4L)
[1] 00 00 00 00
get_value(v, 5L)
[1] 00 00 00 80
get_value(v, 6L)
[1] 01 00 00 00
get_value(v, 7L)
[1] 01 00 00 00
get_value(v, 8L)
[1] 01 00 00 00

Nous vérifions bien avec le code ci-dessus que les vecteurs booléens de R utilisent 4 octets :

  • Les valeurs TRUE sont représentées par 01, 00, 00, 00.
  • Les valeurs FALSE sont représentées par 00, 00, 00, 00.
  • Les valeurs NA sont représentées par 00, 00, 00, 80.

Et il y a beaucoup de bits inutiles…

object.size(rep(v, 10000L)) / 10000L # 9 * 4 bytes de uint32
36 bytes

La taille du vecteur v est de 36 octets, car il contient 9 booléens représentés sous formes d’entiers 32 bits (4 octets).

Sous Arrow

Sous arrow, les vecteurs booléens sont représentés par deux buffers bit par bit.

library(arrow)

Attachement du package : 'arrow'
L'objet suivant est masqué depuis 'package:utils':

    timestamp
donnees <- arrow_array(v)
d <- donnees$data()
buff1 <- d$buffers[[1L]]$data()
buff2 <- d$buffers[[2L]]$data()

buff1
[1] db 01
# 1101 1011 0000 0001
# 0000 0001 1101 1011 en inversant le little endian
# Emplacement (en partant de la droite) des valeurs non nulles.
buff2
[1] c3 01
# 1100 0011 0000 0001
# 0000 0001 1100 0011 en inversant le little endian
# Emplacement des valeurs positives.

Nous pouvons observer le contenu des deux buffers :

  • buff1 contient db, 01. Cela correspond à 1101 1011 0000 0001 en binaire, soit 0000 0001 1101 1011 en convention little-endian (inversion de l’ordre des octets). Nous pouvons retrouver, en partant de la droite, l’emplacement des valeurs non-nulles.
  • buff2 contient c3, 01. Cela correspond à 1100 0011 0000 0001 en binaire, soit 0000 0001 1100 0011 en convention little-endian. Nous pouvons retrouver, en partant de la droite, l’emplacement des valeurs positives.

Il apparaît immédiatement que ce format de données est plus économe.

arrow_array(rep(v, 10000L))$nbytes() / 10000L
[1] 2.25
# 2,250 bytes
# 9/8 de byte pour les NA
# 9/8 de byte pour les TRUE/FALSE

Ici nous obtenons un vecteur de 2,250 octet. En effet. Il y a 9 valeurs représentées chacune par un bit (donc un huitième d’octet) de valeurs non-nulles et un bit de valeurs positives.

Conclusion

Lorsque l’on s’attarde sur les vecteurs booléens, arrow est clairement meilleur que R avec son format bitwise !

Vecteur entier

Sous R

Un vecteur integer sous R correspond à un simple array d’int32 en C.

v <- c(-1L, 10L, NA_integer_, -27000L, 42L, NA_integer_)

code <- "
SEXP res = PROTECT(NEW_RAW(4));
uint32_t val = INTEGER(x)[INTEGER(i)[0]];
memcpy(RAW(res), &val, 4);
UNPROTECT(1);
return res;
"
get_value <- cfunction(signature(x = "character", i = "integer"), code, includes = "#include <stdint.h>")

get_value(v, 0L)
[1] ff ff ff ff
get_value(v, 1L)
[1] 0a 00 00 00
get_value(v, 2L)
[1] 00 00 00 80
get_value(v, 3L)
[1] 88 96 ff ff
get_value(v, 4L)
[1] 2a 00 00 00
get_value(v, 5L)
[1] 00 00 00 80

Comme on le voit ci-dessus, la représentation est celle d’un classique int32 avec un complément à deux. Les octets sont à lire de gauche à droite (et non de droite à gauche comme les nombres arithmétiques) car la plupart des architectures modernes sont little-endian. On note que la valeur correspondant à NA_integer_ est 00, 00, 00, 80. Cette valeur correspond au nombre entier −2147483648, qui est normalement le plus petit nombre négatif qui peut être obtenu sur 32 bits.

Note

Si on tape -2147483648L dans une console R, il y a un warning, et le type de données utilisées devient un double. En effet, comme on l’a vu, cette valeur est déjà utilisée pour représenter le NA_integer_. Le plus petit entier dans R est donc -2147483647L.

object.size(rep(v, 10000L)) / 10000L # 6 * 4 bytes de int32
24 bytes

La taille du vecteur v est de 24 octets, car il contient 6 entier 32 bits.

Sous Arrow

donnees <- arrow_array(v)
d <- donnees$data()
buff1 <- d$buffers[[1L]]$data()
buff2 <- d$buffers[[2L]]$data()

buff1
[1] 1b
# 1101 1011 0000 0001
# 0000 0001 1101 1011 en inversant le little endian
# Emplacement (en partant de la droite) des valeurs non nulles.
buff2
 [1] ff ff ff ff 0a 00 00 00 00 00 00 80 88 96 ff ff 2a 00 00 00 00 00 00 80
# 1100 0011 0000 0001
# 0000 0001 1100 0011 en inversant le little endian
# Emplacement des valeurs positives.

Nous pouvons observer le contenu des deux buffers :

  • buff1 contient 1b. Cela correspond à 0001 1011 en binaire. On retrouve, comme pour les booléens, un masque bit par bit qui représente les valeurs non-NA.
  • buff2 contient ff, ff, ff, ff, 0a, 00, 00, 00, 00, 00, 00, 80, 88, 96, ff, ff, 2a, 00, 00, 00, 00, 00, 00, 80. Cela correspond, exactement comme dans R, à un array d’entiers 32 bits signés représentés en complément à deux.
arrow_array(rep(v, 10000L))$nbytes() / 10000L
[1] 24.75
# 24,75 bytes
# 6 * 4 bytes de int32
# 6/8 de byte pour indiquer les valeurs non NA

Ici nous obtenons un vecteur de 24,75 octet. C’est légèrement supérieur à la représentation R.

Note 
arrow_array(Scalar$create(-2147483647L, type = int32()) - 1, type = int32())
Array
<int32>
[
  -2147483648
]

La valeur non-NA -2147483648 peut être représentée en int32 sous arrow, alors qu’elle ne peut pas l’être sous R.

Tip 
v <- c(-1L, 10L, 2L, 21L)
arrow_array(v, type = int8())
Array
<int8>
[
  -1,
  10,
  2,
  21
]

Comme sous d’autres écosystèmes tels que numpy, arrow permet de choisir des entiers d’autres tailles que 32 bits, ce qui n’est pas permis sous R.

L’on peut ainsi, par exemple, choisir des petits entiers int8() (entiers signés de -128 à 127) ou uint8() (entiers positifs de 0 à 255), tant pour optimiser la taille que pour permettre aux optimisations SIMD d’accélerer le traitement. En effet, une instruction SIMD sur des entiers 8 bits prendra 4 fois mois de temps que sur des entiers 32 bits.

À l’inverse, on peut également utiliser des int64() ou des uint64() si les données manipulées ne tiennent pas sur des entiers 32 bits.

Conclusion

Lorsque l’on s’attarde sur les vecteurs booléens, arrow et R sont très comparables et correspondent essentiellement en des array d’entiers. Cependant, contrairement à R, arrow permet de choisir des entiers de tailles différentes de 32 bits.

Vecteur character

Sous R

Un vecteur character sous R est, en interne, un pointeur vers la global string pool, à savoir un répertoire de chaînes de caractères. La global string pool est alimentée de manière dynamique. Cette représentation a l’avantage de la déduplication, ce qui est pertinent en statistiques dans lesquelles les répétitions sont fréquentes.

v <- c("arnaud", "arnaud", "titouan",NA_character_, "titouan")

code <- "
uintptr_t addr = (uintptr_t)CHAR(STRING_ELT(x, INTEGER(i)[0]));
SEXP res = PROTECT(R_MakeExternalPtr((void*)addr, R_NilValue, R_NilValue));
UNPROTECT(1);
return res;
"
get_adresse <- cfunction(signature(x = "character", i = "integer"), code)

Dans la mesure où nous travaillons avec des pointeurs, nous allons maintenant comparer l’adresse des différents termes.

get_adresse(v, 0L)
<pointer: 0x000002b24a156a18>
get_adresse(v, 1L)
<pointer: 0x000002b24a156a18>

Ici, l’adresse du premier terme "arnaud" est similaire à celle du deuxième "arnaud".

get_adresse(v, 2L)
<pointer: 0x000002b24a156970>
get_adresse(v, 4L)
<pointer: 0x000002b24a156970>

De même, les deux "titouan" ont même adresse.

code <- "
const char* mot = (const char*) R_ExternalPtrAddr(i);
SEXP res = PROTECT(NEW_CHARACTER(1));
SEXP ma_chaine = Rf_mkChar(mot);
SET_STRING_ELT(res, 0, ma_chaine);
UNPROTECT(1);
return res;
"
get_string <- cfunction(signature(i = "externalptr"), code);
adresse <- get_adresse(v, 0L)
get_string(adresse)
[1] "arnaud"

En construisant un nouveau vecteur character dans C à partir de la valeur pointée par <pointer: 0x000002b24a156a18>, on peut vérifier que l’adresse pointe bien vers une chaine de caractères C qui contient arnaud. Nous avons illustré la présence de la global string pool.

object.size(rep(v, 10000L)) / 10000L # 5 * 8 bytes pointeur
40 bytes

La taille observée du vecteur character en mémoire est de 208 bytes (nous utilisons des gros vecteurs avec rep() pour éliminer l’influence fixe des metadata).

Cela correspond à 5 * 8 = 40 octets issus des pointeurs (en architecture 64 bits, chaque pointeur correspond à 8 octets et nous avons 5 valeurs). Les 7 octets issus de la string "arnaud" (6 caractères plus un "\0" final) et 8 octets issus de la string "titouan" tendent comme les metadata vers une influencent nulle dans le total lorsque le vecteur devient grand devant le nombre de modalités.

Sous Arrow

donnees <- arrow_array(v)
d <- donnees$data()
raw_to_uint32 <- function(raw_vec) {
  n <- length(raw_vec)
  nb_blocks <- floor(n / 4)
  
  sapply(seq(1, nb_blocks*4, by=4), function(i) {
    bytes <- raw_vec[i:(i+3)]
    sum(as.numeric(bytes) * 256^(0:3))  # little-endian
  })
}
buff1 <- d$buffers[[1L]]$data()
buff2 <- d$buffers[[2L]]$data()
buff3 <- d$buffers[[3L]]$data()
buff1
[1] 17
buff2
 [1] 00 00 00 00 06 00 00 00 0c 00 00 00 13 00 00 00 13 00 00 00 1a 00 00 00
raw_to_uint32(buff2)
[1]  0  6 12 19 19 26
buff3
 [1] 61 72 6e 61 75 64 61 72 6e 61 75 64 74 69 74 6f 75 61 6e 74 69 74 6f 75 61
[26] 6e
rawToChar(buff3)
[1] "arnaudarnaudtitouantitouan"

En arrow, la représentation des données est plus directe et rudimentaire :

  • buff1 donne l’emplacement des valeurs non NA. Ici cela correspond à 17, soit 0001 0111. En commençant par la droite, on retrouve bien l’emplacement des valeurs non-nulles.
  • buff3 stocke l’intégralité des chaines de caractères concaténées. Ici cela correspond à 61, 72, 6e, 61, 75, 64, 61, 72, 6e, 61, 75, 64, 74, 69, 74, 6f, 75, 61, 6e, 74, 69, 74, 6f, 75, 61, 6e qui se lit donc arnaudarnaudtitouantitouan. Le format est moins complexe que celui de R et nous n’avons pas de déduplication.
  • buff2 donne, à l’aide d’un entier non-signé, l’emplacement des débuts de string dans le buffer buff3. Ici cela correspond à 00, 00, 00, 00, 06, 00, 00, 00, 0c, 00, 00, 00, 13, 00, 00, 00, 13, 00, 00, 00, 1a, 00, 00, 00 que l’on peut décoder en 0, 6, 12, 19, 19, 26.
arrow_array(rep(v, 10000L))$nbytes() / 10000L
[1] 46.625
# 46,625 bytes
# 2 * 6 bytes pour "arnaud"
# 2 * 7 bytes pour "titouan"
# 5 / 8 bytes pour les NA
# 5 * 4 bytes pour les positions de début de string

La taille observée pour ce vecteur au format arrow est de 46,625 octets. Il y a en effet :

  • 2 * 6 octets pour stocker les deux "arnaud"
  • 2 * 7 octets pour stocker les deux "titouan"
  • 5 huitième d’octets pour stocker l’emplacement des NA (un bit par valeur)
  • 5 * 4 octets pour les positions de début dé string (un uint32 correspond à 4 octets).

Conclusion

Nous observons que le format de données arrow n’est pas magique et peut parfois être moins économe en mémoire : ici R est plus économe !!!!

Note

Si les chaines de caractères faisaient moins de 4 caractères chacune en moyenne, le format arrow serait plus économe. En effet, un entier de 32 bit (4 octet) additionné à 4 octets de contenu correspond à la taille d’un pointeur de 64 bits.

De même, dans le cas de vecteurs caractères non répétitifs (comme un identifiant SIREN par exemple), alors le format de données utilisé par R devient nettement moins avantageux, car il ajoute 8 octets de pointeur à chaque valeur, sans pour autant tirer avantage des capacités de déduplication.

Un tibble avec principalement des double et des entiers

Pour synthèse, nous allons comparer un tibble avec principalement des double et des entiers, dans R et dans arrow. Nous utiliserons le tibble flights issue du package nycflights13.

library(tibble)
library(nycflights13)
tbl <- flights
object.size(tbl)
40650104 bytes
ar <- arrow_table(tbl)
ar$nbytes()
[1] 39975481

Nous constatons que la taille du tibble est de 41 Mo, contre 40 Mo pour la taille de la table arrow. Cest sensiblement la même taille comme on manipule des double et des entiers dont la représentation en arrow et en R est similaire.

ar_opti_schema <-
  schema(
    field("year", uint16()),
    field("month", uint8()),
    field("day", uint8()),
    field("dep_time", uint16()),
    field("sched_dep_time", uint16()),
    field("dep_delay", int16()),
    field("arr_time", uint16()),
    field("sched_arr_time", uint16()),
    field("arr_delay", int16()),
    field("carrier", string()),
    field("flight", uint16()),
    field("tailnum", string()),
    field("origin", string()),
    field("dest", string()),
    field("air_time", float()),
    field("distance", float()),
    field("hour", float()),
    field("minute", float()),
    field("time_hour", timestamp(unit = "s"))
  )
ar_opti <- arrow_table(tbl,
                       schema = ar_opti_schema)
ar_opti$nbytes()
[1] 24483785

Nous pouvons cependant réduire un peu la taille de la table arrow, en s’aidant de la disponibilité dans arrow des formats d’entiers et de flottants de taille inférieure à int32 et double.