roaringbitmap/swiftroaring

A better compressed bitset in Swift http://roaringbitmap.org/

SwiftRoaring

Swift wrapper for CRoaring (a C/C++ implementation at https://github.com/RoaringBitmap/CRoaring)

Roaring bitmaps are used by several important systems:

• Apache Lucene and derivative systems such as Solr and Elastic,
• Metamarkets' Druid,
• Apache Spark,
• Netflix Atlas,
• LinkedIn Pinot,
• OpenSearchServer,
• Cloud Torrent,
• Whoosh,
• Pilosa,
• Microsoft Visual Studio Team Services (VSTS),
• eBay's Apache Kylin.

Roaring bitmaps are found to work well in many important applications:

Use Roaring for bitmap compression whenever possible. Do not use other bitmap compression methods (Wang et al., SIGMOD 2017)

Dependencies

Swift 4.0 or higher

Usage using Swift Package Manager

Create a directory where you will create your application:

mkdir foo
cd foo
swift package init --type executable

Then edit Package.swift so that it reads something like this:

import PackageDescription

let package = Package(
    name: "foo",
    dependencies: [
   .package(url: "https://github.com/RoaringBitmap/SwiftRoaring",  from: "0.0.1")
    ],
    targets: [
        .target(
            name: "foo",
            dependencies: ["SwiftRoaring"]),
    ]
)

Edit main.swift (in Sources) so that it looks something like this :

import SwiftRoaring;

....

Example

Here is a simplified but complete example:

import SwiftRoaring

//Create a new Roaring Bitmap
let bitmap = RoaringBitmap()

//Example: Add Range
bitmap.addRange(min: 0, max: 500)

//Example: copy
let cpy = bitmap.copy()

//Example: Operators
let and = bitmap && cpy

//Example: Iterate
for i in bitmap {
    print(i)
}

//See documentation for more functionalities!

Development

You can build using Swift Package Manager as follows:

swift build  --configuration release

To find where the library is built, type the following in your shell:

 echo $(swift build   --configuration release  --show-bin-path)

You can run tests using Swift Package Manager as follows:

swift test

Interactive use

$ swift build  --configuration release
$ swift repl -I .build/release -L .build/release -lSwiftRoaringDynamic
  1> import SwiftRoaring
  2> let bitmap = RoaringBitmap()
  3> bitmap.add(1)
  4> for i in bitmap {
       print(i)
     }

Mailing list/discussion group

https://groups.google.com/forum/#!forum/roaring-bitmaps

Compatibility with Java RoaringBitmap library

You can read bitmaps in Go, Java, C, C++ that have been serialized in Java, C, C++.

References

• Daniel Lemire, Owen Kaser, Nathan Kurz, Luca Deri, Chris O'Hara, François Saint-Jacques, Gregory Ssi-Yan-Kai, Software: Practice and Experience Volume 48, Issue 4 April 2018 Pages 867-895 arXiv:1709.07821
• Samy Chambi, Daniel Lemire, Owen Kaser, Robert Godin, Better bitmap performance with Roaring bitmaps, Software: Practice and Experience Volume 46, Issue 5, pages 709–719, May 2016 http://arxiv.org/abs/1402.6407 This paper used data from http://lemire.me/data/realroaring2014.html
• Daniel Lemire, Gregory Ssi-Yan-Kai, Owen Kaser, Consistently faster and smaller compressed bitmaps with Roaring, Software: Practice and Experience Volume 46, Issue 11, pages 1547-1569, November 2016 http://arxiv.org/abs/1603.06549

swiftroaring's Issues

Confusing semantics of maximum

I'm confused by the intended semantics of max. In the following example, we have two sets, one which contains a zero and one which is empty. However max returns 0 in both cases. How can I distinguish these cases? Am I supposed to be checking if the set is empty?

func testFirst() {
    // empty
    let a: RoaringBitmap = []
    print("empty")
    for e in a {
        print(e)
    }
    print("a max", a.max())

    // empty
    print("has 0")
    let b: RoaringBitmap = [0]
    for e in b {
        print(e)
    }

    print("b max", b.max())
}

Swift - RoaringBitmap - Serialize to base64

Hello, I am trying to serialise a bloom filter generated in a roaring bitmap format to a base64 string, so that I can save it in MongoDB. But the function portableSerialize is a bit tricky for me.

I am so far just testing how it works and I generate a random bloom filter values that I later try to convert to buffer -> to data -> to base64:

func generateBloomFilterData(){
    let bitmap = RoaringBitmap()
    for i in 0..<50 { 
        let random = arc4random_uniform(2)
        if random == 0 {
            bitmap.add(UInt32(i))
        } 
    }  
    let count = (Int(bitmap.count) * MemoryLayout<Int8>.size)
    var buffer = [Int8](repeating: 0, count: count)
    _ = bitmap.portableSerialize(buffer: &buffer)
    let uintBuffer = buffer.map { UInt8(bitPattern: $0) }
    let bufferData = Data(uintBuffer)
    let base64String = bufferData()
    print("buffer size: \(buffer.count), \(uintBuffer.count), base64: \(bufferData.base64EncodedString())")
    //-> send base64 string to database
}

This generates an error:

malloc: MallocStackLogging: attempting to release an index out of
bounds

The console shows:

buffer size: 20, 20, base64: OjAAAAEAAAAAABMAEAAAAAMABQA=

Is there a way how to simply generate a base64 string out of the above generated RoaringBitmap() ?

Use fastbase64 for encoding

Hello, did you consider adding support for base64 encoding to roaring? I imagine that fastbase64 would do the trick.

This is probably more of a croaring issue that SwiftRoaring but we discussed base64 encoding here.