34:["$","title",null,{"children":"Array Filtering - Apache Arrow vs. GPU.js Textures vs. Array.filter vs. Lodash | Robert Plummer | Observable"}] 3c:T4e4,gpuFilterStats = { let count = 0; const gpu = new GPU.GPU({ mode: 'webgl2' }); const predicate = gpu.createKernel(function(proto, startPort, endPort, isActive) { if ( proto[this.thread.x] === 6 && (startPort[this.thread.x] > 0 && endPort[this.thread.x] < 200 || startPort[this.thread.x] === 49152) && isActive[this.thread.x] === 1 ) { return 1; } return 0; }) .setOutput([policies.length]) .setPipeline(true); const toTexture = gpu.createKernel(function(array) { return array[this.thread.x]; }, { output: [policies.length], pipeline: true }); const protosTexture = toTexture(protos); const startPortsTexture = toTexture(startPorts); const endPortsTexture = toTexture(endPorts); const isActivesTexture = toTexture(isActives); predicate.build(protosTexture, startPortsTexture, endPortsTexture, isActivesTexture); const forceSync = gpu.createKernel(function() { return 1; }, { output: [1] }); forceSync.build(); const t1 = performance.now(); const result = predicate(protosTexture, startPortsTexture, endPortsTexture, isActivesTexture); forceSync(); const t2 = performance.now(); return { result: result, count: d3.sum(result.toArray()), ms: t2 - t1 }; }3d:[{"id":"155f638235fd6760dae17e8c893742dcc08a593bdc971bdde881eccad854b4829ded099698f921276ab2d3650cd23c3be25b28ebfa352255210ffaa4f41b2e81","href":"https://static.observableusercontent.com/files/155f638235fd6760dae17e8c893742dcc08a593bdc971bdde881eccad854b4829ded099698f921276ab2d3650cd23c3be25b28ebfa352255210ffaa4f41b2e81","name":"all-policies.json","type":"application/json","lastModified":1583539286952.956,"size":6427816}] 38:{"id":"12a357df686a3ec2","slug":"array-filtering-apache-arrow-vs-gpu-js-textures-vs-array-fil","title":"Array Filtering - Apache Arrow vs. GPU.js Textures vs. Array.filter vs. Lodash","thumbnail":"15b6b8fdefdcdc61fbcbbc75216cc65b5a5412512dd24e95f8740a4566d80580","access_level":"public","create_time":"$D2020-03-07T00:01:26.952Z","update_time":"$D2020-03-07T00:03:43.689Z","view_time":null,"first_public_time":"$D2020-03-07T00:03:47.429Z","has_unpublished_edits":null,"fork":{"id":"d23eff05766b65e4","slug":"array-filtering-apache-arrow-vs-gpu-js-vs-array-filter","title":"Array Filtering - Apache Arrow vs. GPU.js vs. Array.filter vs. Lodash","owner":{"id":"beaaca19380524ca","login":"rusackas","name":"Evan Rusackas"}},"stars":5,"starred":false,"owner":{"type":"team","id":"72acb2c0d5f42f07","login":"robertleeplummerjr","name":"Robert Plummer","avatar_url":"https://avatars-next.observableusercontent.com/29cc2d2e197244c0c5f6f0d48fe6ea1c3d6f3525cfcb4909c8f296200306192f","tier":"starter_2024","bio":"","followed_by_you":false,"follows_you":false},"version":380,"publish_version":380,"role":null,"authored":false,"authors":[{"type":"individual","id":"c577c23eddc09d7d","login":"robertleeplummerjr","name":"Robert Plummer","avatar_url":"https://avatars-next.observableusercontent.com/29cc2d2e197244c0c5f6f0d48fe6ea1c3d6f3525cfcb4909c8f296200306192f","tier":null,"bio":"","followed_by_you":false,"follows_you":false}],"members":[{"type":"individual","id":"c577c23eddc09d7d","login":"robertleeplummerjr","name":"Robert Plummer","avatar_url":"https://avatars-next.observableusercontent.com/29cc2d2e197244c0c5f6f0d48fe6ea1c3d6f3525cfcb4909c8f296200306192f","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"lapsed":null,"subscribed":null,"forks":3,"collection":null,"type":"notebook","body":{"titling":"auto","title":"Array Filtering - Apache Arrow vs. GPU.js Textures vs. Array.filter vs. Lodash","cells":[{"id":0,"value":"md`# Array Filtering - Apache Arrow vs. GPU.js Textures vs. Array.filter vs. Lodash`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":327,"value":"md`This is just a fork of a notebook written by Duane Barlow, who is cooler than me. I just added some performance improvements suggested by Mike Bostock, threw in Lodash for curiosity's sake, and leveraged high resolution time for fun. Curiously, Lodash wins! 🏆`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":2,"value":"md`\nIn each test, we filter ${commas(policies.length)} rows of data with the shape:\n\n

\n\\`\\`\\`\n{\n  proto, // Uint8\n  startPort, // Uint16\n  endPort, // Uint16\n  isActive // Boolean\n}\n\\`\\`\\`\n

\n\nOne test uses Apache Arrow, which uses a columnar flat-array implementation, another test uses GPU.js to filter the array on the GPU. I'm really interested in feedback on this approach, and if anyone has ideas for improving it. The other test uses \\`Array.filter\\` on an array-of-objects. Each test applies the equivalent of the following filter:\n\n

\n\\`\\`\\`\n(\n  proto == 6 &&\n  (startPort > 0 && endPort < 200 || startPort == 49152) &&\n  isActive == true\n)\n\\`\\`\\`\n

\n\n**The vanilla Array-of-objects.filter consistently out-performs both Apache Arrow and GPU.js. Is this expected? In what cases would we expect Arrow filtering to be faster? How about GPU.js?**\n\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":130,"value":"md`\n| Method (filtering ${commas(policiesTable.count())} rows) | Matching Rows | Filter Time | Comparison\n|--------|-------|------:|------:|\n| Apache Arrow | ${commas(arrowFilterStats.count)} | ${commas(arrowFilterStats.ms.toFixed(decimals))} ms | ${xFactor(arrowFilterStats.ms)} |\n| GPU.js | ${commas(gpuFilterStats.count)} | ${commas(gpuFilterStats.ms.toFixed(decimals))} ms | ${xFactor(gpuFilterStats.ms)} |\n| Array.filter | ${commas(arrayFilterStats.count)} | ${commas(arrayFilterStats.ms.toFixed(decimals))} ms | ${xFactor(arrayFilterStats.ms)} |\n| Lodash.filter | ${commas(lodashFilterStats.count)} | ${commas(lodashFilterStats.ms.toFixed(decimals))} ms | ${xFactor(lodashFilterStats.ms)} |\n\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":198,"value":"md`## Code`;","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":120,"value":"arrowFilterStats = {\n const t1 = performance.now();\n \n const count = policiesTable.filter(\n arrow.predicate.and(\n arrow.predicate.col('proto').eq(6),\n arrow.predicate.or(\n arrow.predicate.and(\n arrow.predicate.col('startPort').gt(0),\n arrow.predicate.col('endPort').lt(200)\n ),\n arrow.predicate.col('startPort').eq(49152)\n ),\n arrow.predicate.col('isActive').eq(true)\n )\n ).count();\n \n const t2 = performance.now();\n return {\n count,\n ms: t2 - t1\n };\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":257,"value":"$3c","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":110,"value":"arrayFilterStats = {\n \n const predicate = policy => {\n return policy.proto === 6\n && ((policy.startPort > 0 && policy.endPort < 200) || policy.startPort === 49152)\n && policy.isActive === true;\n };\n const t1 = performance.now();\n \n const count = policies.filter(predicate).length;\n \n const t2 = performance.now();\n \n return {\n count,\n ms: t2 - t1\n };\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":317,"value":"lodashFilterStats = {\n \n const predicate = policy => {\n return policy.proto === 6\n && ((policy.startPort > 0 && policy.endPort < 200) || policy.startPort === 49152)\n && policy.isActive === true;\n };\n const t1 = performance.now();\n \n const count = _(policies).filter(predicate).value().length;\n \n const t2 = performance.now();\n \n return {\n count,\n ms: t2 - t1\n };\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":348,"value":"viewof decimals=slider({step: 1,min:0,max:13,value: 3,title: 'number of decimals in result times'})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":357,"value":"winningTime = Math.min(lodashFilterStats.ms, arrayFilterStats.ms, arrowFilterStats.ms, gpuFilterStats.ms);","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":356,"value":"xFactor = (value) => {\n if(value === winningTime) return '🏆'\n else{\n const multiple = value/winningTime;\n return multiple.toFixed(1) + 'x';\n }\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":11,"value":"policiesJson = {\n return FileAttachment(\"all-policies.json\").json();\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":60,"value":"policies = {\n let values = policiesJson.map(policy => {\n const portParts = policy.port.split('-').map(port => +port);\n policy.startPort = portParts[0];\n policy.endPort = portParts.length === 1 ? portParts[0] : portParts[1];\n const consumerParts = policy.consumer.split(':');\n const providerParts = policy.provider.split(':');\n policy.consumerShort = consumerParts[consumerParts.length - 1];\n policy.providerShort = providerParts[providerParts.length - 1];\n return policy;\n });\n const NUMBER_OF_DUPLICATES = 50;\n const finalValues = [];\n for (let i = 0; i < NUMBER_OF_DUPLICATES; i++) {\n for (let j = 0; j < values.length; j++) {\n const policy = values[j];\n policy.isActive = Math.random() > .3;\n finalValues.push({ ...policy });\n }\n }\n return finalValues;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":54,"value":"policiesTable = arrow.Table.new(\n [\n arrow.Uint8Vector.from(protos),\n arrow.Uint16Vector.from(startPorts),\n arrow.Uint16Vector.from(endPorts),\n arrow.BoolVector.from(isActives)\n ],\n ['proto', 'startPort', 'endPort', 'isActive']\n)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":74,"value":"protos = policies.map(policy => policy.proto)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":77,"value":"startPorts = policies.map(policy => policy.startPort)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":80,"value":"endPorts = policies.map(policy => policy.endPort)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":83,"value":"isActives = policies.map(policy => policy.isActive)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":289,"value":"isActiveInts = policies.map(policy => policy.isActive ? 1 : 0)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":86,"value":"consumers = policies.map(policy => policy.consumer)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":89,"value":"providers = policies.map(policy => policy.provider)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":13,"value":"md`## Dependencies`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":7,"value":"arrow = require('apache-arrow')","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":144,"value":"d3 = require('d3')","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":318,"value":"_ = require(\"lodash@4\");","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":146,"value":"commas = d3.format(',');","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":262,"value":"GPU = require(\"gpu.js@2\")","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":345,"value":"import {slider} from \"@jashkenas/inputs\"","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W3d","stdlib":"1"}} 33:null