31:T596,md`# Faster Arrow Dictionary Unpacking String operations in Apache Arrow for Javascript are extraordinarily slow compared to the rest of the library. Arrow stores strings in a UInt8 array, and on the browsers I've used it takes a very long time (like, a millisecond) to convert each individual string. When unpacking dictionary objects, arrow's Javascript implementation decodes each of the dictionary entries for each row, which guarantees relatively low memory use. But if there are only a few dictionary keys, this can be extremely expensive. The code shows that you can get a 100x speedup in converting some sample data to strings if you only decode the dictionary keys, and then assign them to a javascript array from the integer values. I believe I'm handling null values correctly, but I may miss some cases. A third, in-between option is to continue using the backing integer array, but to materialize the dictionary cache on demand. In the example here, this takes somewhere in between in time; it will have a *much* smaller memory footprint than strategy 1, and is potentially worth adopting inside the Arrow project itself. Materializing the dictionary first appears to have no benefits, so the other advantages of on-demand materialization make it a clear winner. This properly handles the null field where it exists through some fancy bit operations, but may not perform properly on non-nullable dictionaries. `32:T535,{ let results = "# Benchmark" yield md`${results}` restart let start = Date.now() let v1 = unpack_dictionary_column(tab.getColumn("country")) const t1 = Date.now() - start; results += `\n**${t1}**ms for unpacking the entire dictionary up front...\n` yield md`${results}` const start3 = Date.now() const col2 = tab.getColumn("country2") bless_getter_with_cache(col2) const v3 = new Array(col2.length) for (let i = 0; i < col2.length; i++) { v3[i] = col2.get(i) } const t3 = Date.now() - start3; results += `\n**${t3}** for on-demand materialization of the dictionary...\n` yield md`${results}` const start5 = Date.now() const col3 = tab.getColumn("country3") bless_getter_with_cache(col3, true) const v4 = new Array(col3.length) for (let i = 0; i < col3.length; i++) { v3[i] = col3.get(i) } const t5 = Date.now() - start5; results += `\n**${t5}** for pre-materialization of the dictionary...\n` yield md`${results}` const start2 = Date.now() let v2 = tab.getColumn("country").toArray() const t2 = Date.now() - start2; results += `\n**${t2}** for builtin arrow toArray()\n` yield md`${results}` for (let i = 0; i < v3.length; i++) { if (v1[i] != v3[i] || v1[i] != fake_data[0][i]) { yield "BUT THEY'RE NOT THE SAME!" } } }33:[] 2f:{"title":"Faster Arrow Dictionary Unpacking","cells":[{"id":0,"value":"$31","pinned":false,"hidden":false,"mode":"ojs"},{"id":128,"value":"$32","pinned":false,"hidden":false,"mode":"ojs"},{"id":129,"value":"viewof restart = html``","pinned":false,"hidden":false,"mode":"ojs"},{"id":5,"value":"function unpack_dictionary_column(column) {\n // Column -- an arrow column Dictionary vector.\n const codes = new Array(column.length)\n const ks = column.chunks[column.chunks.length-1].dictionary.toArray()\n let i = 0;\n for (const chunk of column.chunks) {\n const nullmap = chunk.nullBitmap || [];\n for (let j=0; j < chunk.data.length; j++) {\n const ix = chunk.data.values[j]\n // Fancy bit operations because the null masks pack 8 observations into each bit.\n // ix >> 3 advances the byte every 8 bits; \n // (1 << (ix % 8) checks if the bit is set for the particular position inside the byte.\n \n // You must check nullmap.length because if there are no null values in a chunk,\n // the nullmap doesn't exist.\n if (nullmap.length && !(nullmap[j >> 3] & (1 << (j % 8)))) {\n codes[i] = null\n } else {\n codes[i] = ks[ix]\n }\n i++\n }\n }\n return codes\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":19,"value":"LENGTH = 1e6 // Total elements in the dictionary column","pinned":true,"hidden":false,"mode":"ojs"},{"id":480,"value":"cardinality = 1e2 // Number of different keys in the dictionary","pinned":true,"hidden":false,"mode":"ojs"},{"id":496,"value":"string_length = 25 // Length of the keys in the dictionary","pinned":true,"hidden":false,"mode":"ojs"},{"id":482,"value":"function random_string(length) {\n let o = \"\"\n while (o.length < length) {\n o += String.fromCharCode(Math.random() * 52 + 48)\n }\n return o\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":17,"value":"fake_data = {\n const d = new Array(LENGTH)\n const e = new Array(LENGTH)\n \n const values = []\n const populations = []\n while (values.length < cardinality) {\n values.push(random_string(string_length))\n populations.push(Math.random() * 1e9)\n }\n let i = 0;\n while (i++ < LENGTH) {\n const ix = (Math.floor(Math.random() * values.length))\n if (i < LENGTH/2 && Math.random() < .1) {\n d[i-1] = null\n e[i-1] = -1\n } else {\n d[i-1] = values[ix]\n e[i-1] = populations[ix]\n }\n }\n\n return [d, e]\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":162,"value":"tab.getColumn(\"population\").toArray() // Note the -1 s here--that means toArray() is missing the nulls.","pinned":true,"hidden":false,"mode":"ojs"},{"id":9,"value":"tab = arrow.Table.new(\n // data\n [arrow.Vector.from({\n values: fake_data[0],\n type: new arrow.Dictionary(new arrow.Utf8(), new arrow.Int32()),\n }),arrow.Vector.from({\n values: fake_data[0],\n type: new arrow.Dictionary(new arrow.Utf8(), new arrow.Int32()),\n }),arrow.Vector.from({\n values: fake_data[0],\n type: new arrow.Dictionary(new arrow.Utf8(), new arrow.Int32()),\n }),\n arrow.Vector.from({\n values: fake_data[1],\n type: new arrow.Float32()\n })\n ],\n [\"country\", \n \"country2\",\n \"country3\",\n \"population\"]\n)","pinned":true,"hidden":false,"mode":"ojs"},{"id":295,"value":"function is_it_null(i, nullmap) {\n return nullmap && nullmap.length &&\n (!(nullmap[i >> 3] & (1 << (i % 8))))\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":247,"value":"g = tab.getColumn(\"country2\")","pinned":true,"hidden":false,"mode":"ojs"},{"id":327,"value":"fake_data[0]","pinned":true,"hidden":false,"mode":"ojs"},{"id":418,"value":"f = [1,2,3]","pinned":true,"hidden":false,"mode":"ojs"},{"id":415,"value":"{\n return f[2] = 8\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":232,"value":"function bless_getter_with_cache(col, pre_create = false) {\n if (!col.dictionary) {return}\n if (!col._materialized_dictionary) {\n col._materialized_dictionary = [] \n }\n if (pre_create) {\n col._materialized_dictionary = col.chunks[col.chunks.length-1].dictionary.toArray()\n }\n col.get = function(i) {\n const ix = col.indices.get(i);\n if (ix === null) {return ix}\n const v = col._materialized_dictionary[ix]\n return v ? \n v : \n col._materialized_dictionary[ix] = col.dictionary.get(ix)\n }\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":220,"value":"col = tab.getColumn(\"country\")","pinned":true,"hidden":false,"mode":"ojs"},{"id":584,"value":"col.I","pinned":true,"hidden":false,"mode":"ojs"},{"id":95,"value":"{\n // Make sure it's working.\n return false\n const unpacked = unpack_dictionary_column(tab.getColumn(\"country\"))\n for (let i = 0; i < fake_data.length; i++) {\n if (fake_data[0][i] != unpacked[i]) {\n yield [i, fake_data[0][i], unpacked[i]]\n break\n }\n }\n} ","pinned":true,"hidden":false,"mode":"ojs"},{"id":547,"value":"t = new TextDecoder()","pinned":true,"hidden":false,"mode":"ojs"},{"id":552,"value":"garray = {\n const beginning = Date.now()\n let start = null\n let end = null\n const data = []\n const chunk = col.chunks[col.chunks.length - 1]\n for (let offset of chunk.dictionary.data.valueOffsets) {\n if (start !== null) {\n const t = new TextDecoder()\n data.push(t.decode(chunk.dictionary.data.values.slice(start, offset)))\n }\n start = offset\n }\n return {time: Date.now() - beginning, data: data}\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":2,"value":"arrow = require(\"apache-arrow@0.17\")","pinned":true,"hidden":false,"mode":"ojs"}],"files":"$W33","stdlib":"1","titling":"auto"}