SFVInt: Simple, Fast and Generic Variable-Length Integer Decoding using Bit Manipulation Instructions Article Swipe
Gang Liao
,
Ye Liu
,
Yonghua Ding
,
Le Cai
,
Jianjun Chen
·
YOU?
·
· 2024
· Open Access
·
· DOI: https://doi.org/10.1145/3662010.3663439
YOU?
·
· 2024
· Open Access
·
· DOI: https://doi.org/10.1145/3662010.3663439
The ubiquity of variable-length integers in data storage and communication necessitates efficient decoding techniques. In this paper, we present SFVInt, a simple and fast approach to decode the prevalent Little Endian Base-128 (LEB128) varints. Our approach effectively utilizes the Bit Manipulation Instruction Set 2 (BMI2) in modern Intel and AMD processors, achieving significant performance improvement while maintaining simplicity and avoiding overengineering. SFVInt, with its generic design, effectively processes both 32-bit and 64-bit unsigned integers using a unified code template, marking a significant leap forward in varint decoding efficiency. We thoroughly evaluate SFVInt's performance across various datasets and scenarios, demonstrating that it achieves up to a 2x increase in decoding speed when compared to varint decoding methods used in established frameworks like Facebook Folly and Google Protobuf.
Related Topics
Concepts
Metadata
- Type
- article
- Language
- en
- Landing Page
- https://doi.org/10.1145/3662010.3663439
- OA Status
- gold
- References
- 11
- Related Works
- 10
- OpenAlex ID
- https://openalex.org/W4399163584
All OpenAlex metadata
Raw OpenAlex JSON
- OpenAlex ID
-
https://openalex.org/W4399163584Canonical identifier for this work in OpenAlex
- DOI
-
https://doi.org/10.1145/3662010.3663439Digital Object Identifier
- Title
-
SFVInt: Simple, Fast and Generic Variable-Length Integer Decoding using Bit Manipulation InstructionsWork title
- Type
-
articleOpenAlex work type
- Language
-
enPrimary language
- Publication year
-
2024Year of publication
- Publication date
-
2024-05-30Full publication date if available
- Authors
-
Gang Liao, Ye Liu, Yonghua Ding, Le Cai, Jianjun ChenList of authors in order
- Landing page
-
https://doi.org/10.1145/3662010.3663439Publisher landing page
- Open access
-
YesWhether a free full text is available
- OA status
-
goldOpen access status per OpenAlex
- OA URL
-
https://doi.org/10.1145/3662010.3663439Direct OA link when available
- Concepts
-
Decoding methods, Integer (computer science), Computer science, Simple (philosophy), Variable (mathematics), Bit (key), Algorithm, Arithmetic, Parallel computing, Mathematics, Programming language, Computer network, Mathematical analysis, Epistemology, PhilosophyTop concepts (fields/topics) attached by OpenAlex
- Cited by
-
0Total citation count in OpenAlex
- References (count)
-
11Number of works referenced by this work
- Related works (count)
-
10Other works algorithmically related by OpenAlex
Full payload
| id | https://openalex.org/W4399163584 |
|---|---|
| doi | https://doi.org/10.1145/3662010.3663439 |
| ids.doi | https://doi.org/10.1145/3662010.3663439 |
| ids.openalex | https://openalex.org/W4399163584 |
| fwci | 0.0 |
| type | article |
| title | SFVInt: Simple, Fast and Generic Variable-Length Integer Decoding using Bit Manipulation Instructions |
| biblio.issue | |
| biblio.volume | |
| biblio.last_page | 9 |
| biblio.first_page | 1 |
| topics[0].id | https://openalex.org/T11269 |
| topics[0].field.id | https://openalex.org/fields/17 |
| topics[0].field.display_name | Computer Science |
| topics[0].score | 0.9998999834060669 |
| topics[0].domain.id | https://openalex.org/domains/3 |
| topics[0].domain.display_name | Physical Sciences |
| topics[0].subfield.id | https://openalex.org/subfields/1702 |
| topics[0].subfield.display_name | Artificial Intelligence |
| topics[0].display_name | Algorithms and Data Compression |
| topics[1].id | https://openalex.org/T11130 |
| topics[1].field.id | https://openalex.org/fields/17 |
| topics[1].field.display_name | Computer Science |
| topics[1].score | 0.9976999759674072 |
| topics[1].domain.id | https://openalex.org/domains/3 |
| topics[1].domain.display_name | Physical Sciences |
| topics[1].subfield.id | https://openalex.org/subfields/1702 |
| topics[1].subfield.display_name | Artificial Intelligence |
| topics[1].display_name | Coding theory and cryptography |
| topics[2].id | https://openalex.org/T11321 |
| topics[2].field.id | https://openalex.org/fields/17 |
| topics[2].field.display_name | Computer Science |
| topics[2].score | 0.994700014591217 |
| topics[2].domain.id | https://openalex.org/domains/3 |
| topics[2].domain.display_name | Physical Sciences |
| topics[2].subfield.id | https://openalex.org/subfields/1705 |
| topics[2].subfield.display_name | Computer Networks and Communications |
| topics[2].display_name | Error Correcting Code Techniques |
| is_xpac | False |
| apc_list | |
| apc_paid | |
| concepts[0].id | https://openalex.org/C57273362 |
| concepts[0].level | 2 |
| concepts[0].score | 0.78476881980896 |
| concepts[0].wikidata | https://www.wikidata.org/wiki/Q576722 |
| concepts[0].display_name | Decoding methods |
| concepts[1].id | https://openalex.org/C97137487 |
| concepts[1].level | 2 |
| concepts[1].score | 0.7053256034851074 |
| concepts[1].wikidata | https://www.wikidata.org/wiki/Q729138 |
| concepts[1].display_name | Integer (computer science) |
| concepts[2].id | https://openalex.org/C41008148 |
| concepts[2].level | 0 |
| concepts[2].score | 0.679175615310669 |
| concepts[2].wikidata | https://www.wikidata.org/wiki/Q21198 |
| concepts[2].display_name | Computer science |
| concepts[3].id | https://openalex.org/C2780586882 |
| concepts[3].level | 2 |
| concepts[3].score | 0.6403967142105103 |
| concepts[3].wikidata | https://www.wikidata.org/wiki/Q7520643 |
| concepts[3].display_name | Simple (philosophy) |
| concepts[4].id | https://openalex.org/C182365436 |
| concepts[4].level | 2 |
| concepts[4].score | 0.6092798709869385 |
| concepts[4].wikidata | https://www.wikidata.org/wiki/Q50701 |
| concepts[4].display_name | Variable (mathematics) |
| concepts[5].id | https://openalex.org/C117011727 |
| concepts[5].level | 2 |
| concepts[5].score | 0.4652923345565796 |
| concepts[5].wikidata | https://www.wikidata.org/wiki/Q1278488 |
| concepts[5].display_name | Bit (key) |
| concepts[6].id | https://openalex.org/C11413529 |
| concepts[6].level | 1 |
| concepts[6].score | 0.43862926959991455 |
| concepts[6].wikidata | https://www.wikidata.org/wiki/Q8366 |
| concepts[6].display_name | Algorithm |
| concepts[7].id | https://openalex.org/C94375191 |
| concepts[7].level | 1 |
| concepts[7].score | 0.4322391450405121 |
| concepts[7].wikidata | https://www.wikidata.org/wiki/Q11205 |
| concepts[7].display_name | Arithmetic |
| concepts[8].id | https://openalex.org/C173608175 |
| concepts[8].level | 1 |
| concepts[8].score | 0.3637159764766693 |
| concepts[8].wikidata | https://www.wikidata.org/wiki/Q232661 |
| concepts[8].display_name | Parallel computing |
| concepts[9].id | https://openalex.org/C33923547 |
| concepts[9].level | 0 |
| concepts[9].score | 0.22425681352615356 |
| concepts[9].wikidata | https://www.wikidata.org/wiki/Q395 |
| concepts[9].display_name | Mathematics |
| concepts[10].id | https://openalex.org/C199360897 |
| concepts[10].level | 1 |
| concepts[10].score | 0.09822627902030945 |
| concepts[10].wikidata | https://www.wikidata.org/wiki/Q9143 |
| concepts[10].display_name | Programming language |
| concepts[11].id | https://openalex.org/C31258907 |
| concepts[11].level | 1 |
| concepts[11].score | 0.07388821244239807 |
| concepts[11].wikidata | https://www.wikidata.org/wiki/Q1301371 |
| concepts[11].display_name | Computer network |
| concepts[12].id | https://openalex.org/C134306372 |
| concepts[12].level | 1 |
| concepts[12].score | 0.0 |
| concepts[12].wikidata | https://www.wikidata.org/wiki/Q7754 |
| concepts[12].display_name | Mathematical analysis |
| concepts[13].id | https://openalex.org/C111472728 |
| concepts[13].level | 1 |
| concepts[13].score | 0.0 |
| concepts[13].wikidata | https://www.wikidata.org/wiki/Q9471 |
| concepts[13].display_name | Epistemology |
| concepts[14].id | https://openalex.org/C138885662 |
| concepts[14].level | 0 |
| concepts[14].score | 0.0 |
| concepts[14].wikidata | https://www.wikidata.org/wiki/Q5891 |
| concepts[14].display_name | Philosophy |
| keywords[0].id | https://openalex.org/keywords/decoding-methods |
| keywords[0].score | 0.78476881980896 |
| keywords[0].display_name | Decoding methods |
| keywords[1].id | https://openalex.org/keywords/integer |
| keywords[1].score | 0.7053256034851074 |
| keywords[1].display_name | Integer (computer science) |
| keywords[2].id | https://openalex.org/keywords/computer-science |
| keywords[2].score | 0.679175615310669 |
| keywords[2].display_name | Computer science |
| keywords[3].id | https://openalex.org/keywords/simple |
| keywords[3].score | 0.6403967142105103 |
| keywords[3].display_name | Simple (philosophy) |
| keywords[4].id | https://openalex.org/keywords/variable |
| keywords[4].score | 0.6092798709869385 |
| keywords[4].display_name | Variable (mathematics) |
| keywords[5].id | https://openalex.org/keywords/bit |
| keywords[5].score | 0.4652923345565796 |
| keywords[5].display_name | Bit (key) |
| keywords[6].id | https://openalex.org/keywords/algorithm |
| keywords[6].score | 0.43862926959991455 |
| keywords[6].display_name | Algorithm |
| keywords[7].id | https://openalex.org/keywords/arithmetic |
| keywords[7].score | 0.4322391450405121 |
| keywords[7].display_name | Arithmetic |
| keywords[8].id | https://openalex.org/keywords/parallel-computing |
| keywords[8].score | 0.3637159764766693 |
| keywords[8].display_name | Parallel computing |
| keywords[9].id | https://openalex.org/keywords/mathematics |
| keywords[9].score | 0.22425681352615356 |
| keywords[9].display_name | Mathematics |
| keywords[10].id | https://openalex.org/keywords/programming-language |
| keywords[10].score | 0.09822627902030945 |
| keywords[10].display_name | Programming language |
| keywords[11].id | https://openalex.org/keywords/computer-network |
| keywords[11].score | 0.07388821244239807 |
| keywords[11].display_name | Computer network |
| language | en |
| locations[0].id | doi:10.1145/3662010.3663439 |
| locations[0].is_oa | True |
| locations[0].source | |
| locations[0].license | cc-by |
| locations[0].pdf_url | |
| locations[0].version | publishedVersion |
| locations[0].raw_type | proceedings-article |
| locations[0].license_id | https://openalex.org/licenses/cc-by |
| locations[0].is_accepted | True |
| locations[0].is_published | True |
| locations[0].raw_source_name | Proceedings of the 20th International Workshop on Data Management on New Hardware |
| locations[0].landing_page_url | https://doi.org/10.1145/3662010.3663439 |
| indexed_in | crossref |
| authorships[0].author.id | https://openalex.org/A5035138733 |
| authorships[0].author.orcid | https://orcid.org/0000-0002-8280-9094 |
| authorships[0].author.display_name | Gang Liao |
| authorships[0].countries | US |
| authorships[0].affiliations[0].institution_ids | https://openalex.org/I66946132 |
| authorships[0].affiliations[0].raw_affiliation_string | ByteDance Infrastructure System Lab, USA and University of Maryland College Park |
| authorships[0].institutions[0].id | https://openalex.org/I66946132 |
| authorships[0].institutions[0].ror | https://ror.org/047s2c258 |
| authorships[0].institutions[0].type | education |
| authorships[0].institutions[0].lineage | https://openalex.org/I66946132 |
| authorships[0].institutions[0].country_code | US |
| authorships[0].institutions[0].display_name | University of Maryland, College Park |
| authorships[0].author_position | first |
| authorships[0].raw_author_name | Gang Liao |
| authorships[0].is_corresponding | False |
| authorships[0].raw_affiliation_strings | ByteDance Infrastructure System Lab, USA and University of Maryland College Park |
| authorships[1].author.id | https://openalex.org/A5084799859 |
| authorships[1].author.orcid | https://orcid.org/0009-0003-7959-172X |
| authorships[1].author.display_name | Ye Liu |
| authorships[1].affiliations[0].raw_affiliation_string | ByteDance Infrastructure System Lab, USA |
| authorships[1].author_position | middle |
| authorships[1].raw_author_name | Ye Liu |
| authorships[1].is_corresponding | False |
| authorships[1].raw_affiliation_strings | ByteDance Infrastructure System Lab, USA |
| authorships[2].author.id | https://openalex.org/A5024624933 |
| authorships[2].author.orcid | https://orcid.org/0000-0002-9124-6107 |
| authorships[2].author.display_name | Yonghua Ding |
| authorships[2].affiliations[0].raw_affiliation_string | ByteDance Infrastructure System Lab, USA |
| authorships[2].author_position | middle |
| authorships[2].raw_author_name | Yonghua Ding |
| authorships[2].is_corresponding | False |
| authorships[2].raw_affiliation_strings | ByteDance Infrastructure System Lab, USA |
| authorships[3].author.id | https://openalex.org/A5045627881 |
| authorships[3].author.orcid | https://orcid.org/0000-0002-0656-2691 |
| authorships[3].author.display_name | Le Cai |
| authorships[3].affiliations[0].raw_affiliation_string | ByteDance Infrastructure System Lab, USA |
| authorships[3].author_position | middle |
| authorships[3].raw_author_name | Le Cai |
| authorships[3].is_corresponding | False |
| authorships[3].raw_affiliation_strings | ByteDance Infrastructure System Lab, USA |
| authorships[4].author.id | https://openalex.org/A5100410508 |
| authorships[4].author.orcid | https://orcid.org/0000-0002-3734-892X |
| authorships[4].author.display_name | Jianjun Chen |
| authorships[4].affiliations[0].raw_affiliation_string | ByteDance Infrastructure System Lab, USA |
| authorships[4].author_position | last |
| authorships[4].raw_author_name | Jianjun Chen |
| authorships[4].is_corresponding | False |
| authorships[4].raw_affiliation_strings | ByteDance Infrastructure System Lab, USA |
| has_content.pdf | False |
| has_content.grobid_xml | False |
| is_paratext | False |
| open_access.is_oa | True |
| open_access.oa_url | https://doi.org/10.1145/3662010.3663439 |
| open_access.oa_status | gold |
| open_access.any_repository_has_fulltext | False |
| created_date | 2025-10-10T00:00:00 |
| display_name | SFVInt: Simple, Fast and Generic Variable-Length Integer Decoding using Bit Manipulation Instructions |
| has_fulltext | False |
| is_retracted | False |
| updated_date | 2025-11-06T03:46:38.306776 |
| primary_topic.id | https://openalex.org/T11269 |
| primary_topic.field.id | https://openalex.org/fields/17 |
| primary_topic.field.display_name | Computer Science |
| primary_topic.score | 0.9998999834060669 |
| primary_topic.domain.id | https://openalex.org/domains/3 |
| primary_topic.domain.display_name | Physical Sciences |
| primary_topic.subfield.id | https://openalex.org/subfields/1702 |
| primary_topic.subfield.display_name | Artificial Intelligence |
| primary_topic.display_name | Algorithms and Data Compression |
| related_works | https://openalex.org/W2411923897, https://openalex.org/W4394546135, https://openalex.org/W4285347720, https://openalex.org/W4200259850, https://openalex.org/W2333831899, https://openalex.org/W2484894494, https://openalex.org/W2367385042, https://openalex.org/W4381186982, https://openalex.org/W2040781570, https://openalex.org/W4226055750 |
| cited_by_count | 0 |
| locations_count | 1 |
| best_oa_location.id | doi:10.1145/3662010.3663439 |
| best_oa_location.is_oa | True |
| best_oa_location.source | |
| best_oa_location.license | cc-by |
| best_oa_location.pdf_url | |
| best_oa_location.version | publishedVersion |
| best_oa_location.raw_type | proceedings-article |
| best_oa_location.license_id | https://openalex.org/licenses/cc-by |
| best_oa_location.is_accepted | True |
| best_oa_location.is_published | True |
| best_oa_location.raw_source_name | Proceedings of the 20th International Workshop on Data Management on New Hardware |
| best_oa_location.landing_page_url | https://doi.org/10.1145/3662010.3663439 |
| primary_location.id | doi:10.1145/3662010.3663439 |
| primary_location.is_oa | True |
| primary_location.source | |
| primary_location.license | cc-by |
| primary_location.pdf_url | |
| primary_location.version | publishedVersion |
| primary_location.raw_type | proceedings-article |
| primary_location.license_id | https://openalex.org/licenses/cc-by |
| primary_location.is_accepted | True |
| primary_location.is_published | True |
| primary_location.raw_source_name | Proceedings of the 20th International Workshop on Data Management on New Hardware |
| primary_location.landing_page_url | https://doi.org/10.1145/3662010.3663439 |
| publication_date | 2024-05-30 |
| publication_year | 2024 |
| referenced_works | https://openalex.org/W2151131744, https://openalex.org/W3174518099, https://openalex.org/W2032866865, https://openalex.org/W2758508602, https://openalex.org/W4381329140, https://openalex.org/W2055774867, https://openalex.org/W4388041443, https://openalex.org/W2062666276, https://openalex.org/W1982013147, https://openalex.org/W2409939811, https://openalex.org/W1985136582 |
| referenced_works_count | 11 |
| abstract_inverted_index.2 | 43 |
| abstract_inverted_index.a | 20, 75, 80, 104 |
| abstract_inverted_index.2x | 105 |
| abstract_inverted_index.In | 14 |
| abstract_inverted_index.We | 88 |
| abstract_inverted_index.in | 5, 45, 84, 107, 117 |
| abstract_inverted_index.it | 100 |
| abstract_inverted_index.of | 2 |
| abstract_inverted_index.to | 25, 103, 112 |
| abstract_inverted_index.up | 102 |
| abstract_inverted_index.we | 17 |
| abstract_inverted_index.AMD | 49 |
| abstract_inverted_index.Bit | 39 |
| abstract_inverted_index.Our | 34 |
| abstract_inverted_index.Set | 42 |
| abstract_inverted_index.The | 0 |
| abstract_inverted_index.and | 8, 22, 48, 58, 70, 96, 123 |
| abstract_inverted_index.its | 63 |
| abstract_inverted_index.the | 27, 38 |
| abstract_inverted_index.both | 68 |
| abstract_inverted_index.code | 77 |
| abstract_inverted_index.data | 6 |
| abstract_inverted_index.fast | 23 |
| abstract_inverted_index.leap | 82 |
| abstract_inverted_index.like | 120 |
| abstract_inverted_index.that | 99 |
| abstract_inverted_index.this | 15 |
| abstract_inverted_index.used | 116 |
| abstract_inverted_index.when | 110 |
| abstract_inverted_index.with | 62 |
| abstract_inverted_index.Folly | 122 |
| abstract_inverted_index.Intel | 47 |
| abstract_inverted_index.speed | 109 |
| abstract_inverted_index.using | 74 |
| abstract_inverted_index.while | 55 |
| abstract_inverted_index.(BMI2) | 44 |
| abstract_inverted_index.32-bit | 69 |
| abstract_inverted_index.64-bit | 71 |
| abstract_inverted_index.Endian | 30 |
| abstract_inverted_index.Google | 124 |
| abstract_inverted_index.Little | 29 |
| abstract_inverted_index.across | 93 |
| abstract_inverted_index.decode | 26 |
| abstract_inverted_index.modern | 46 |
| abstract_inverted_index.paper, | 16 |
| abstract_inverted_index.simple | 21 |
| abstract_inverted_index.varint | 85, 113 |
| abstract_inverted_index.SFVInt, | 19, 61 |
| abstract_inverted_index.design, | 65 |
| abstract_inverted_index.forward | 83 |
| abstract_inverted_index.generic | 64 |
| abstract_inverted_index.marking | 79 |
| abstract_inverted_index.methods | 115 |
| abstract_inverted_index.present | 18 |
| abstract_inverted_index.storage | 7 |
| abstract_inverted_index.unified | 76 |
| abstract_inverted_index.various | 94 |
| abstract_inverted_index.(LEB128) | 32 |
| abstract_inverted_index.Base-128 | 31 |
| abstract_inverted_index.Facebook | 121 |
| abstract_inverted_index.SFVInt's | 91 |
| abstract_inverted_index.achieves | 101 |
| abstract_inverted_index.approach | 24, 35 |
| abstract_inverted_index.avoiding | 59 |
| abstract_inverted_index.compared | 111 |
| abstract_inverted_index.datasets | 95 |
| abstract_inverted_index.decoding | 12, 86, 108, 114 |
| abstract_inverted_index.evaluate | 90 |
| abstract_inverted_index.increase | 106 |
| abstract_inverted_index.integers | 4, 73 |
| abstract_inverted_index.ubiquity | 1 |
| abstract_inverted_index.unsigned | 72 |
| abstract_inverted_index.utilizes | 37 |
| abstract_inverted_index.varints. | 33 |
| abstract_inverted_index.Protobuf. | 125 |
| abstract_inverted_index.achieving | 51 |
| abstract_inverted_index.efficient | 11 |
| abstract_inverted_index.prevalent | 28 |
| abstract_inverted_index.processes | 67 |
| abstract_inverted_index.template, | 78 |
| abstract_inverted_index.frameworks | 119 |
| abstract_inverted_index.scenarios, | 97 |
| abstract_inverted_index.simplicity | 57 |
| abstract_inverted_index.thoroughly | 89 |
| abstract_inverted_index.Instruction | 41 |
| abstract_inverted_index.effectively | 36, 66 |
| abstract_inverted_index.efficiency. | 87 |
| abstract_inverted_index.established | 118 |
| abstract_inverted_index.improvement | 54 |
| abstract_inverted_index.maintaining | 56 |
| abstract_inverted_index.performance | 53, 92 |
| abstract_inverted_index.processors, | 50 |
| abstract_inverted_index.significant | 52, 81 |
| abstract_inverted_index.techniques. | 13 |
| abstract_inverted_index.Manipulation | 40 |
| abstract_inverted_index.necessitates | 10 |
| abstract_inverted_index.communication | 9 |
| abstract_inverted_index.demonstrating | 98 |
| abstract_inverted_index.variable-length | 3 |
| abstract_inverted_index.overengineering. | 60 |
| cited_by_percentile_year | |
| countries_distinct_count | 1 |
| institutions_distinct_count | 5 |
| citation_normalized_percentile.value | 0.0742798 |
| citation_normalized_percentile.is_in_top_1_percent | False |
| citation_normalized_percentile.is_in_top_10_percent | False |