Repository: pilosa/pilosa
Pull request #1974 (2019-05-13 22:05:09)

WIP: Improve row cache (mostly by not doing it)
The row cache turns out to use a lot of memory, especially in read-heavy loads. On relatively write-heavy loads, the row cache gets flushed moderately frequently, implicitly, by the periodic snapshots. On read-heavy loads, though, it grows without any upper bound but "the number of rows you have". Furthermore, to avoid corruption or data races, it has *copies* of the data. This doesn't just double the storage requirements -- in the case where a lot of the data is mmapped from files, the mapped pages can be dropped by the kernel and re-read later, but copies made from that data  can't be dropped like that.

In order to address this, we adopt copy-on-write semantics. (Note: This isn't actually fully implemented yet.) The basic idea is that containers acquire Freeze and Thaw methods; Freeze gives you a container that you can trust no one else will modify, and Thaw gives you a container you can safely modify. As of now, Freeze sets a flag, and Thaw does a copy.

To make this work, all operations that might mutate containers now return new containers (or pointers to them, anyway), and things like the add/remove operations on bitmaps now stash updated containers back into the bitmaps. Missing, as of yet, is the part where, when putting something in the row cache, we freeze its contents. I knew I was forgetting something.

As a secondary component of this work, I've also implemented (partially) support for nil containers as valid (but innately-frozen) containers, which can be queried in various ways. I'm not totally sure that was actually necessary, but it fits with the general pattern implied by following an `append`-like rule. Basically, since you can do `s = append(s, ...)` for a nil slice, I wanted `c = c.add(v)` to work for a nil container.

Fixes # 1968



Patch:
diff --git a/cache.go b/cache.go
index 40509ab6..0bf4cd09 100644
--- a/cache.go
+++ b/cache.go
@@ -452,9 +452,14 @@ func (s *simpleCache) Fetch(id uint64) (*Row, bool) {
 	return m, ok
 }
 
-// Add adds the bitmap to the cache, keyed on the id.
+// Add adds the bitmap to the cache, keyed on the id. A nil row means
+// deleting the row from the cache.
 func (s *simpleCache) Add(id uint64, b *Row) {
-	s.cache[id] = b
+	if b != nil {
+		s.cache[id] = b
+	} else {
+		delete(s.cache, id)
+	}
 }
 
 // nopCache represents a no-op Cache implementation.
diff --git a/enterprise/b/btree.go b/enterprise/b/btree.go
deleted file mode 100644
index 2fa5c24e..00000000
--- a/enterprise/b/btree.go
+++ /dev/null
@@ -1,953 +0,0 @@
-// This file is a modified redistribution of b (https://github.com/cznic/b),
-// which is governed by the following license notice:
-//
-// Copyright (c) 2014 The b Authors. All rights reserved.
-//
-// Redistribution and use in source and binary forms, with or without
-// modification, are permitted provided that the following conditions are
-// met:
-//
-//    * Redistributions of source code must retain the above copyright
-// notice, this list of conditions and the following disclaimer.
-//    * Redistributions in binary form must reproduce the above
-// copyright notice, this list of conditions and the following disclaimer
-// in the documentation and/or other materials provided with the
-// distribution.
-//    * Neither the names of the authors nor the names of the
-// contributors may be used to endorse or promote products derived from
-// this software without specific prior written permission.
-//
-// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
-// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
-// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
-// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
-// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
-// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
-// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
-// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
-// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
-// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
-// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
-
-package b
-
-import (
-	"io"
-	"sync"
-
-	"github.com/pilosa/pilosa/roaring"
-)
-
-const (
-	// kx must be >= 2
-	kx = 128 //TODO benchmark tune this number if using custom key/value type(s).
-	// kd must be >= 1
-	kd = 128 //TODO benchmark tune this number if using custom key/value type(s).
-)
-
-var (
-	btDPool = sync.Pool{New: func() interface{} { return &d{} }}
-	btEPool = btEpool{sync.Pool{New: func() interface{} { return &enumerator{} }}}
-	btTPool = btTpool{sync.Pool{New: func() interface{} { return &tree{} }}}
-	btXPool = sync.Pool{New: func() interface{} { return &x{} }}
-)
-
-type btTpool struct{ sync.Pool }
-
-func (p *btTpool) get(cmp Cmp) *tree {
-	x := p.Get().(*tree)
-	x.cmp = cmp
-	return x
-}
-
-type btEpool struct{ sync.Pool }
-
-func (p *btEpool) get(err error, hit bool, i int, k uint64, q *d, t *tree, ver int64) *enumerator {
-	x := p.Get().(*enumerator)
-	x.err, x.hit, x.i, x.k, x.q, x.t, x.ver = err, hit, i, k, q, t, ver
-	return x
-}
-
-type (
-	// Cmp compares a and b. Return value is:
-	//
-	//	< 0 if a <  b
-	//	  0 if a == b
-	//	> 0 if a >  b
-	//
-	Cmp func(a, b uint64) int64
-
-	d struct { // data page
-		c int
-		d [2*kd + 1]de
-		n *d
-		p *d
-	}
-
-	de struct { // d element
-		k uint64
-		v *roaring.Container
-	}
-
-	// enumerator captures the state of enumerating a tree. It is returned
-	// from the Seek* methods. The enumerator is aware of any mutations
-	// made to the tree in the process of enumerating it and automatically
-	// resumes the enumeration at the proper key, if possible.
-	//
-	// However, once an enumerator returns io.EOF to signal "no more
-	// items", it does no more attempt to "resync" on tree mutation(s).  In
-	// other words, io.EOF from an enumerator is "sticky" (idempotent).
-	enumerator struct {
-		err error
-		hit bool
-		i   int
-		k   uint64
-		q   *d
-		t   *tree
-		ver int64
-	}
-
-	// tree is a B+tree.
-	tree struct {
-		c     int
-		cmp   Cmp
-		first *d
-		last  *d
-		r     interface{}
-		ver   int64
-	}
-
-	xe struct { // x element
-		ch interface{}
-		k  uint64
-	}
-
-	x struct { // index page
-		c int
-		x [2*kx + 2]xe
-	}
-)
-
-var ( // R/O zero values
-	zd  d
-	zde de
-	ze  enumerator
-	zk  uint64
-	zt  tree
-	zx  x
-	zxe xe
-)
-
-func clr(q interface{}) {
-	switch x := q.(type) {
-	case *x:
-		for i := 0; i <= x.c; i++ { // Ch0 Sep0 ... Chn-1 Sepn-1 Chn
-			clr(x.x[i].ch)
-		}
-		*x = zx
-		btXPool.Put(x)
-	case *d:
-		*x = zd
-		btDPool.Put(x)
-	}
-}
-
-// -------------------------------------------------------------------------- x
-
-func newX(ch0 interface{}) *x {
-	r := btXPool.Get().(*x)
-	r.x[0].ch = ch0
-	return r
-}
-
-func (q *x) extract(i int) {
-	q.c--
-	if i < q.c {
-		copy(q.x[i:], q.x[i+1:q.c+1])
-		q.x[q.c].ch = q.x[q.c+1].ch
-		q.x[q.c].k = zk  // GC
-		q.x[q.c+1] = zxe // GC
-	}
-}
-
-func (q *x) insert(i int, k uint64, ch interface{}) *x {
-	c := q.c
-	if i < c {
-		q.x[c+1].ch = q.x[c].ch
-		copy(q.x[i+2:], q.x[i+1:c])
-		q.x[i+1].k = q.x[i].k
-	}
-	c++
-	q.c = c
-	q.x[i].k = k
-	q.x[i+1].ch = ch
-	return q
-}
-
-func (q *x) siblings(i int) (l, r *d) {
-	if i >= 0 {
-		if i > 0 {
-			l = q.x[i-1].ch.(*d)
-		}
-		if i < q.c {
-			r = q.x[i+1].ch.(*d)
-		}
-	}
-	return l, r
-}
-
-// -------------------------------------------------------------------------- d
-
-func (l *d) mvL(r *d, c int) {
-	copy(l.d[l.c:], r.d[:c])
-	copy(r.d[:], r.d[c:r.c])
-	// Zero out the de's here to prevent reading bad data
-	// and to avoid creating non-collectible (GC) references.
-	for i := 1; i < c; i++ {
-		r.d[r.c-i] = zde
-	}
-	l.c += c
-	r.c -= c
-}
-
-func (l *d) mvR(r *d, c int) {
-	copy(r.d[c:], r.d[:r.c])
-	copy(r.d[:c], l.d[l.c-c:])
-	// Zero out the de's here to prevent reading bad data
-	// and to avoid creating non-collectible (GC) references.
-	for i := 1; i < c; i++ {
-		l.d[l.c-c+i] = zde
-	}
-	r.c += c
-	l.c -= c
-}
-
-// ----------------------------------------------------------------------- Tree
-
-// treeNew returns a newly created, empty Tree. The compare function is used
-// for key collation.
-func treeNew(cmp Cmp) *tree {
-	return btTPool.get(cmp)
-}
-
-// Clear removes all K/V pairs from the tree.
-func (t *tree) Clear() {
-	if t.r == nil {
-		return
-	}
-
-	clr(t.r)
-	t.c, t.first, t.last, t.r = 0, nil, nil, nil
-	t.ver++
-}
-
-// Close performs Clear and recycles t to a pool for possible later reuse. No
-// references to t should exist or such references must not be used afterwards.
-func (t *tree) Close() {
-	t.Clear()
-	*t = zt
-	btTPool.Put(t)
-}
-
-func (t *tree) cat(p *x, q, r *d, pi int) {
-	t.ver++
-	q.mvL(r, r.c)
-	if r.n != nil {
-		r.n.p = q
-	} else {
-		t.last = q
-	}
-	q.n = r.n
-	*r = zd
-	btDPool.Put(r)
-	if p.c > 1 {
-		p.extract(pi)
-		p.x[pi].ch = q
-		return
-	}
-
-	switch x := t.r.(type) {
-	case *x:
-		*x = zx
-		btXPool.Put(x)
-	case *d:
-		*x = zd
-		btDPool.Put(x)
-	}
-	t.r = q
-}
-
-func (t *tree) catX(p, q, r *x, pi int) {
-	t.ver++
-	q.x[q.c].k = p.x[pi].k
-	copy(q.x[q.c+1:], r.x[:r.c])
-	q.c += r.c + 1
-	q.x[q.c].ch = r.x[r.c].ch
-	*r = zx
-	btXPool.Put(r)
-	if p.c > 1 {
-		p.c--
-		pc := p.c
-		if pi < pc {
-			p.x[pi].k = p.x[pi+1].k
-			copy(p.x[pi+1:], p.x[pi+2:pc+1])
-			p.x[pc].ch = p.x[pc+1].ch
-			p.x[pc].k = zk     // GC
-			p.x[pc+1].ch = nil // GC
-		}
-		return
-	}
-
-	switch x := t.r.(type) {
-	case *x:
-		*x = zx
-		btXPool.Put(x)
-	case *d:
-		*x = zd
-		btDPool.Put(x)
-	}
-	t.r = q
-}
-
-// Delete removes the k's KV pair, if it exists, in which case Delete returns
-// true.
-func (t *tree) Delete(k uint64) (ok bool) {
-	pi := -1
-	var p *x
-	q := t.r
-	if q == nil {
-		return false
-	}
-
-	for {
-		var i int
-		i, ok = t.find(q, k)
-		if ok {
-			switch x := q.(type) {
-			case *x:
-				if x.c < kx && q != t.r {
-					x, i = t.underflowX(p, x, pi, i)
-				}
-				pi = i + 1
-				p = x
-				q = x.x[pi].ch
-				continue
-			case *d:
-				t.extract(x, i)
-				if x.c >= kd {
-					return true
-				}
-
-				if q != t.r {
-					t.underflow(p, x, pi)
-				} else if t.c == 0 {
-					t.Clear()
-				}
-				return true
-			}
-		}
-
-		switch x := q.(type) {
-		case *x:
-			if x.c < kx && q != t.r {
-				x, i = t.underflowX(p, x, pi, i)
-			}
-			pi = i
-			p = x
-			q = x.x[i].ch
-		case *d:
-			return false
-		}
-	}
-}
-
-func (t *tree) extract(q *d, i int) { // (r *container) {
-	t.ver++
-	//r = q.d[i].v // prepared for Extract
-	q.c--
-	if i < q.c {
-		copy(q.d[i:], q.d[i+1:q.c+1])
-	}
-	q.d[q.c] = zde // GC
-	t.c--
-}
-
-func (t *tree) find(q interface{}, k uint64) (i int, ok bool) {
-	var mk uint64
-	l := 0
-	switch x := q.(type) {
-	case *x:
-		h := x.c - 1
-		for l <= h {
-			m := (l + h) >> 1
-			mk = x.x[m].k
-			switch cmp := t.cmp(k, mk); {
-			case cmp > 0:
-				l = m + 1
-			case cmp == 0:
-				return m, true
-			default:
-				h = m - 1
-			}
-		}
-	case *d:
-		h := x.c - 1
-		for l <= h {
-			m := (l + h) >> 1
-			mk = x.d[m].k
-			switch cmp := t.cmp(k, mk); {
-			case cmp > 0:
-				l = m + 1
-			case cmp == 0:
-				return m, true
-			default:
-				h = m - 1
-			}
-		}
-	}
-	return l, false
-}
-
-// First returns the first item of the tree in the key collating order, or
-// (zero-value, zero-value) if the tree is empty.
-func (t *tree) First() (k uint64, v *roaring.Container) {
-	if q := t.first; q != nil {
-		q := &q.d[0]
-		k, v = q.k, q.v
-	}
-	return k, v
-}
-
-// Get returns the value associated with k and true if it exists. Otherwise Get
-// returns (zero-value, false).
-func (t *tree) Get(k uint64) (v *roaring.Container, ok bool) {
-	q := t.r
-	if q == nil {
-		return
-	}
-
-	for {
-		var i int
-		if i, ok = t.find(q, k); ok {
-			switch x := q.(type) {
-			case *x:
-				q = x.x[i+1].ch
-				continue
-			case *d:
-				return x.d[i].v, true
-			}
-		}
-		switch x := q.(type) {
-		case *x:
-			q = x.x[i].ch
-		default:
-			return
-		}
-	}
-}
-
-func (t *tree) insert(q *d, i int, k uint64, v *roaring.Container) *d {
-	t.ver++
-	c := q.c
-	if i < c {
-		copy(q.d[i+1:], q.d[i:c])
-	}
-	c++
-	q.c = c
-	q.d[i].k, q.d[i].v = k, v
-	t.c++
-	return q
-}
-
-// Last returns the last item of the tree in the key collating order, or
-// (zero-value, zero-value) if the tree is empty.
-func (t *tree) Last() (k uint64, v *roaring.Container) {
-	if q := t.last; q != nil {
-		q := &q.d[q.c-1]
-		k, v = q.k, q.v
-	}
-	return k, v
-}
-
-// Len returns the number of items in the tree.
-func (t *tree) Len() int {
-	return t.c
-}
-
-func (t *tree) overflow(p *x, q *d, pi, i int, k uint64, v *roaring.Container) {
-	t.ver++
-	l, r := p.siblings(pi)
-
-	// s is the number of items to shift out of the full data container to
-	// allow for the new data item. This logic shifts by half the available
-	// space plus one. In the case where the new item is to be inserted within
-	// the calculated shift space, then s is reduced to include only the
-	// data items up to the index of the new data item.
-	if l != nil && l.c < 2*kd && i != 0 {
-		s := (2*kd-l.c)/2 + 1 // half plus one
-		//s := 2*kd - l.c // all available
-		if i < s {
-			s = i
-		}
-		l.mvL(q, s)
-		t.insert(q, i-s, k, v)
-		p.x[pi-1].k = q.d[0].k
-		return
-	}
-
-	if r != nil && r.c < 2*kd {
-		if i < 2*kd {
-			s := (2*kd-r.c)/2 + 1 // half plus one
-			//s := 2*kd - r.c // all available
-			if 2*kd-i < s {
-				s = 2*kd - i
-			}
-			q.mvR(r, s)
-			t.insert(q, i, k, v)
-			p.x[pi].k = r.d[0].k
-			return
-		}
-
-		t.insert(r, 0, k, v)
-		p.x[pi].k = k
-		return
-	}
-
-	t.split(p, q, pi, i, k, v)
-}
-
-// Seek returns an Enumerator positioned on an item such that k >= item's key.
-// ok reports if k == item.key The Enumerator's position is possibly after the
-// last item in the tree.
-func (t *tree) Seek(k uint64) (e *enumerator, ok bool) {
-	q := t.r
-	if q == nil {
-		e = btEPool.get(nil, false, 0, k, nil, t, t.ver)
-		return
-	}
-
-	for {
-		var i int
-		if i, ok = t.find(q, k); ok {
-			switch x := q.(type) {
-			case *x:
-				q = x.x[i+1].ch
-				continue
-			case *d:
-				return btEPool.get(nil, ok, i, k, x, t, t.ver), true
-			}
-		}
-
-		switch x := q.(type) {
-		case *x:
-			q = x.x[i].ch
-		case *d:
-			return btEPool.get(nil, ok, i, k, x, t, t.ver), false
-		}
-	}
-}
-
-// SeekFirst returns an enumerator positioned on the first KV pair in the tree,
-// if any. For an empty tree, err == io.EOF is returned and e will be nil.
-func (t *tree) SeekFirst() (e *enumerator, err error) {
-	q := t.first
-	if q == nil {
-		return nil, io.EOF
-	}
-
-	return btEPool.get(nil, true, 0, q.d[0].k, q, t, t.ver), nil
-}
-
-// SeekLast returns an enumerator positioned on the last KV pair in the tree,
-// if any. For an empty tree, err == io.EOF is returned and e will be nil.
-func (t *tree) SeekLast() (e *enumerator, err error) {
-	q := t.last
-	if q == nil {
-		return nil, io.EOF
-	}
-
-	return btEPool.get(nil, true, q.c-1, q.d[q.c-1].k, q, t, t.ver), nil
-}
-
-// Set sets the value associated with k.
-func (t *tree) Set(k uint64, v *roaring.Container) {
-	//dbg("--- PRE Set(%v, %v)\n%s", k, v, t.dump())
-	//defer func() {
-	//	dbg("--- POST\n%s\n====\n", t.dump())
-	//}()
-
-	pi := -1
-	var p *x
-	q := t.r
-	if q == nil {
-		z := t.insert(btDPool.Get().(*d), 0, k, v)
-		t.r, t.first, t.last = z, z, z
-		return
-	}
-
-	for {
-		i, ok := t.find(q, k)
-		if ok {
-			switch x := q.(type) {
-			case *x:
-				i++
-				if x.c > 2*kx {
-					x, i = t.splitX(p, x, pi, i)
-				}
-				pi = i
-				p = x
-				q = x.x[i].ch
-				continue
-			case *d:
-				x.d[i].v = v
-			}
-			return
-		}
-
-		switch x := q.(type) {
-		case *x:
-			if x.c > 2*kx {
-				x, i = t.splitX(p, x, pi, i)
-			}
-			pi = i
-			p = x
-			q = x.x[i].ch
-		case *d:
-			switch {
-			case x.c < 2*kd:
-				t.insert(x, i, k, v)
-			default:
-				t.overflow(p, x, pi, i, k, v)
-			}
-			return
-		}
-	}
-}
-
-// Put combines Get and Set in a more efficient way where the tree is walked
-// only once. The upd(ater) receives (old-value, true) if a KV pair for k
-// exists or (zero-value, false) otherwise. It can then return a (new-value,
-// true) to create or overwrite the existing value in the KV pair, or
-// (whatever, false) if it decides not to create or not to update the value of
-// the KV pair.
-//
-// 	tree.Set(k, v) call conceptually equals calling
-//
-// 	tree.Put(k, func(uint64, bool){ return v, true })
-//
-// modulo the differing return values.
-func (t *tree) Put(k uint64, upd func(oldV *roaring.Container, exists bool) (newV *roaring.Container, write bool)) (oldV *roaring.Container, written bool) {
-	pi := -1
-	var p *x
-	q := t.r
-	var newV *roaring.Container
-	if q == nil {
-		// new KV pair in empty tree
-		newV, written = upd(newV, false)
-		if !written {
-			return
-		}
-
-		z := t.insert(btDPool.Get().(*d), 0, k, newV)
-		t.r, t.first, t.last = z, z, z
-		return
-	}
-
-	for {
-		i, ok := t.find(q, k)
-		if ok {
-			switch x := q.(type) {
-			case *x:
-				i++
-				if x.c > 2*kx {
-					x, i = t.splitX(p, x, pi, i)
-				}
-				pi = i
-				p = x
-				q = x.x[i].ch
-				continue
-			case *d:
-				oldV = x.d[i].v
-				newV, written = upd(oldV, true)
-				if !written {
-					return
-				}
-
-				x.d[i].v = newV
-			}
-			return
-		}
-
-		switch x := q.(type) {
-		case *x:
-			if x.c > 2*kx {
-				x, i = t.splitX(p, x, pi, i)
-			}
-			pi = i
-			p = x
-			q = x.x[i].ch
-		case *d: // new KV pair
-			newV, written = upd(newV, false)
-			if !written {
-				return
-			}
-
-			switch {
-			case x.c < 2*kd:
-				t.insert(x, i, k, newV)
-			default:
-				t.overflow(p, x, pi, i, k, newV)
-			}
-			return
-		}
-	}
-}
-
-func (t *tree) split(p *x, q *d, pi, i int, k uint64, v *roaring.Container) {
-	t.ver++
-	r := btDPool.Get().(*d)
-	if q.n != nil {
-		r.n = q.n
-		r.n.p = r
-	} else {
-		t.last = r
-	}
-	q.n = r
-	r.p = q
-
-	copy(r.d[:], q.d[kd:2*kd])
-	for i := range q.d[kd:] {
-		q.d[kd+i] = zde
-	}
-	q.c = kd
-	r.c = kd
-	var done bool
-	if i > kd {
-		done = true
-		t.insert(r, i-kd, k, v)
-	}
-	if pi >= 0 {
-		p.insert(pi, r.d[0].k, r)
-	} else {
-		t.r = newX(q).insert(0, r.d[0].k, r)
-	}
-	if done {
-		return
-	}
-
-	t.insert(q, i, k, v)
-}
-
-func (t *tree) splitX(p *x, q *x, pi int, i int) (*x, int) {
-	t.ver++
-	r := btXPool.Get().(*x)
-	copy(r.x[:], q.x[kx+1:])
-	q.c = kx
-	r.c = kx
-	if pi >= 0 {
-		p.insert(pi, q.x[kx].k, r)
-	} else {
-		t.r = newX(q).insert(0, q.x[kx].k, r)
-	}
-
-	q.x[kx].k = zk
-	for i := range q.x[kx+1:] {
-		q.x[kx+i+1] = zxe
-	}
-	if i > kx {
-		q = r
-		i -= kx + 1
-	}
-
-	return q, i
-}
-
-func (t *tree) underflow(p *x, q *d, pi int) {
-	t.ver++
-	l, r := p.siblings(pi)
-
-	if l != nil && l.c+q.c >= 2*kd {
-		l.mvR(q, 1)
-		p.x[pi-1].k = q.d[0].k
-		return
-	}
-
-	if r != nil && q.c+r.c >= 2*kd {
-		q.mvL(r, 1)
-		p.x[pi].k = r.d[0].k
-		r.d[r.c] = zde // GC
-		return
-	}
-
-	if l != nil {
-		t.cat(p, l, q, pi-1)
-		return
-	}
-
-	t.cat(p, q, r, pi)
-}
-
-func (t *tree) underflowX(p *x, q *x, pi int, i int) (*x, int) {
-	t.ver++
-	var l, r *x
-
-	if pi >= 0 {
-		if pi > 0 {
-			l = p.x[pi-1].ch.(*x)
-		}
-		if pi < p.c {
-			r = p.x[pi+1].ch.(*x)
-		}
-	}
-
-	if l != nil && l.c > kx {
-		q.x[q.c+1].ch = q.x[q.c].ch
-		copy(q.x[1:], q.x[:q.c])
-		q.x[0].ch = l.x[l.c].ch
-		q.x[0].k = p.x[pi-1].k
-		q.c++
-		i++
-		l.c--
-		p.x[pi-1].k = l.x[l.c].k
-		return q, i
-	}
-
-	if r != nil && r.c > kx {
-		q.x[q.c].k = p.x[pi].k
-		q.c++
-		q.x[q.c].ch = r.x[0].ch
-		p.x[pi].k = r.x[0].k
-		copy(r.x[:], r.x[1:r.c])
-		r.c--
-		rc := r.c
-		r.x[rc].ch = r.x[rc+1].ch
-		r.x[rc].k = zk
-		r.x[rc+1].ch = nil
-		return q, i
-	}
-
-	if l != nil {
-		i += l.c + 1
-		t.catX(p, l, q, pi-1)
-		q = l
-		return q, i
-	}
-
-	t.catX(p, q, r, pi)
-	return q, i
-}
-
-// ----------------------------------------------------------------- Enumerator
-
-// Close recycles e to a pool for possible later reuse. No references to e
-// should exist or such references must not be used afterwards.
-func (e *enumerator) Close() {
-	*e = ze
-	btEPool.Put(e)
-}
-
-// Next returns the currently enumerated item, if it exists and moves to the
-// next item in the key collation order. If there is no item to return, err ==
-// io.EOF is returned.
-func (e *enumerator) Next() (k uint64, v *roaring.Container, err error) {
-	if err = e.err; err != nil {
-		return 0, nil, err
-	}
-
-	if e.ver != e.t.ver {
-		f, _ := e.t.Seek(e.k)
-		*e = *f
-		f.Close()
-	}
-	if e.q == nil {
-		e.err, err = io.EOF, io.EOF
-		return 0, nil, err
-	}
-
-	if e.i >= e.q.c {
-		if err = e.next(); err != nil {
-			return 0, nil, err
-		}
-	}
-
-	i := e.q.d[e.i]
-	k, v = i.k, i.v
-	e.k, e.hit = k, true
-	_ = e.next()
-	return k, v, nil
-}
-
-func (e *enumerator) next() error {
-	if e.q == nil {
-		e.err = io.EOF
-		return io.EOF
-	}
-
-	switch {
-	case e.i < e.q.c-1:
-		e.i++
-	default:
-		if e.q, e.i = e.q.n, 0; e.q == nil {
-			e.err = io.EOF
-		}
-	}
-	return e.err
-}
-
-// Prev returns the currently enumerated item, if it exists and moves to the
-// previous item in the key collation order. If there is no item to return, err
-// == io.EOF is returned.
-func (e *enumerator) Prev() (k uint64, v *roaring.Container, err error) {
-	if err = e.err; err != nil {
-		return 0, nil, err
-	}
-
-	if e.ver != e.t.ver {
-		f, _ := e.t.Seek(e.k)
-		*e = *f
-		f.Close()
-	}
-	if e.q == nil {
-		e.err, err = io.EOF, io.EOF
-		return 0, nil, err
-	}
-
-	if !e.hit {
-		// move to previous because Seek overshoots if there's no hit
-		if err = e.prev(); err != nil {
-			return 0, nil, err
-		}
-	}
-
-	if e.i >= e.q.c {
-		if err = e.prev(); err != nil {
-			return 0, nil, err
-		}
-	}
-
-	i := e.q.d[e.i]
-	k, v = i.k, i.v
-	e.k, e.hit = k, true
-	_ = e.prev()
-	return k, v, err
-}
-
-func (e *enumerator) prev() error {
-	if e.q == nil {
-		e.err = io.EOF
-		return io.EOF
-	}
-
-	switch {
-	case e.i > 0:
-		e.i--
-	default:
-		if e.q = e.q.p; e.q == nil {
-			e.err = io.EOF
-			break
-		}
-
-		e.i = e.q.c - 1
-	}
-	return e.err
-}
diff --git a/enterprise/b/containers_btree.go b/enterprise/b/containers_btree.go
deleted file mode 100644
index a051d7cd..00000000
--- a/enterprise/b/containers_btree.go
+++ /dev/null
@@ -1,212 +0,0 @@
-// Copyright (c) 2018 Pilosa Corp. All rights reserved.
-//
-// This file is part of Pilosa Enterprise Edition.
-//
-// Pilosa Enterprise Edition is free software: you can redistribute it and/or modify
-// it under the terms of the GNU Affero General Public License as published by
-// the Free Software Foundation, either version 3 of the License, or
-// (at your option) any later version.
-//
-// Pilosa Enterprise Edition is distributed in the hope that it will be useful,
-// but WITHOUT ANY WARRANTY; without even the implied warranty of
-// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
-// GNU Affero General Public License for more details.
-//
-// You should have received a copy of the GNU Affero General Public License
-// along with Pilosa Enterprise Edition.  If not, see <http://www.gnu.org/licenses/>.
-
-package b
-
-import (
-	"io"
-
-	"github.com/pilosa/pilosa/roaring"
-)
-
-func cmp(a, b uint64) int64 {
-	return int64(a - b)
-}
-
-type bTreeContainers struct {
-	tree *tree
-
-	lastKey       uint64
-	lastContainer *roaring.Container
-}
-
-func newBTreeContainers() *bTreeContainers {
-	return &bTreeContainers{
-		tree: treeNew(cmp),
-	}
-}
-
-func NewBTreeBitmap(a ...uint64) *roaring.Bitmap {
-	b := &roaring.Bitmap{
-		Containers: newBTreeContainers(),
-	}
-	// TODO: there's no way to report an error here
-	_, _ = b.Add(a...)
-	return b
-}
-
-func (btc *bTreeContainers) Get(key uint64) *roaring.Container {
-	// Check the last* cache for same container.
-	if key == btc.lastKey && btc.lastContainer != nil {
-		return btc.lastContainer
-	}
-
-	var c *roaring.Container
-	el, ok := btc.tree.Get(key)
-	if ok {
-		c = el
-		btc.lastKey = key
-		btc.lastContainer = c
-	}
-	return c
-}
-
-func (btc *bTreeContainers) Put(key uint64, c *roaring.Container) {
-	// If a mapped container is added to the tree, reset the
-	// lastContainer cache so that the cache is not pointing
-	// at a read-only mmap.
-	if c.Mapped() {
-		btc.lastContainer = nil
-	}
-	btc.tree.Set(key, c)
-}
-
-func (u updater) update(oldV *roaring.Container, exists bool) (*roaring.Container, bool) {
-	// update the existing container
-	if exists {
-		oldV.Update(u.containerType, u.n, u.mapped)
-		return oldV, false
-	}
-	cont := roaring.NewContainer()
-	cont.Update(u.containerType, u.n, u.mapped)
-	return cont, true
-}
-
-// this struct is added to prevent the closure locals from being escaped out to the heap
-type updater struct {
-	key           uint64
-	n             int32
-	containerType byte
-	mapped        bool
-}
-
-func (btc *bTreeContainers) PutContainerValues(key uint64, typ byte, n int, mapped bool) {
-	a := updater{key, int32(n), typ, mapped}
-	btc.tree.Put(key, a.update)
-}
-
-func (btc *bTreeContainers) Remove(key uint64) {
-	btc.tree.Delete(key)
-}
-
-func (btc *bTreeContainers) GetOrCreate(key uint64) *roaring.Container {
-	// Check the last* cache for same container.
-	if key == btc.lastKey && btc.lastContainer != nil {
-		return btc.lastContainer
-	}
-
-	btc.lastKey = key
-	v, ok := btc.tree.Get(key)
-	if !ok {
-		cont := roaring.NewContainerArray(nil)
-		btc.tree.Set(key, cont)
-		btc.lastContainer = cont
-		return cont
-	}
-
-	btc.lastContainer = v
-	return btc.lastContainer
-}
-
-func (btc *bTreeContainers) Count() (n uint64) {
-	e, _ := btc.tree.Seek(0)
-	_, c, err := e.Next()
-	for err != io.EOF {
-		n += uint64(c.N())
-		_, c, err = e.Next()
-	}
-	return n
-}
-
-func (btc *bTreeContainers) Clone() roaring.Containers {
-	nbtc := newBTreeContainers()
-
-	itr, err := btc.tree.SeekFirst()
-	if err == io.EOF {
-		return nbtc
-	}
-	for {
-		k, v, err := itr.Next()
-		if err == io.EOF {
-			break
-		}
-		nbtc.tree.Set(k, v.Clone())
-	}
-	return nbtc
-}
-
-func (btc *bTreeContainers) Last() (key uint64, c *roaring.Container) {
-	if btc.tree.Len() == 0 {
-		return 0, nil
-	}
-	k, v := btc.tree.Last()
-	return k, v
-}
-
-func (btc *bTreeContainers) Size() int {
-	return btc.tree.Len()
-}
-
-func (btc *bTreeContainers) Reset() {
-	btc.tree = treeNew(cmp)
-	btc.lastKey = 0
-	btc.lastContainer = nil
-}
-
-func (btc *bTreeContainers) Iterator(key uint64) (citer roaring.ContainerIterator, found bool) {
-	e, ok := btc.tree.Seek(key)
-	if ok {
-		found = true
-	}
-
-	return &btcIterator{
-		e: e,
-	}, found
-}
-
-func (btc *bTreeContainers) Repair() {
-	e, _ := btc.tree.Seek(0)
-	_, c, err := e.Next()
-	for err != io.EOF {
-		c.Repair()
-		_, c, err = e.Next()
-	}
-}
-
-type btcIterator struct {
-	e   *enumerator
-	key uint64
-	val *roaring.Container
-}
-
-func (i *btcIterator) Next() bool {
-
-	k, v, err := i.e.Next()
-	if err == io.EOF {
-		return false
-	}
-	i.key = k
-	i.val = v
-	return true
-}
-
-func (i *btcIterator) Value() (uint64, *roaring.Container) {
-	if i.val == nil {
-		return 0, nil
-	}
-	return i.key, i.val
-}
diff --git a/enterprise/enterprise.go b/enterprise/enterprise.go
index a7522380..f3a89755 100644
--- a/enterprise/enterprise.go
+++ b/enterprise/enterprise.go
@@ -21,13 +21,3 @@
 // "ENTERPRISE=1 make install". These features were dual-licensed separately
 // from Pilosa community edition under the AGPL and Pilosa's commercial license.
 package enterprise
-
-import (
-	"github.com/pilosa/pilosa/enterprise/b"
-	"github.com/pilosa/pilosa/roaring"
-)
-
-func init() { // nolint: gochecknoinits
-	// Replace Bitmap constructor with B+Tree implementation
-	roaring.NewFileBitmap = b.NewBTreeBitmap
-}
diff --git a/fragment.go b/fragment.go
index d9b9e812..eaccf7b8 100644
--- a/fragment.go
+++ b/fragment.go
@@ -422,19 +422,18 @@ func (f *fragment) unprotectedRow(rowID uint64) *Row {
 func (f *fragment) rowFromStorage(rowID uint64) *Row {
 	// Only use a subset of the containers.
 	// NOTE: The start & end ranges must be divisible by container width.
+	//
+	// Note that OffsetRange now returns a new bitmap which uses frozen
+	// containers which will use copy-on-write semantics. The actual bitmap
+	// and Containers object are new and not shared, but the containers are
+	// shared.
 	data := f.storage.OffsetRange(f.shard*ShardWidth, rowID*ShardWidth, (rowID+1)*ShardWidth)
 
-	// Reference bitmap subrange in storage. We Clone() data because otherwise
-	// row will contain pointers to containers in storage. This causes
-	// unexpected results when we cache the row and try to use it later.
-	// Basically, since we return the Row and release the fragment lock, the
-	// underlying fragment storage could be changed or snapshotted and thrown
-	// out at any point.
 	row := &Row{
 		segments: []rowSegment{{
-			data:     *data.Clone(),
+			data:     data,
 			shard:    f.shard,
-			writable: false, // this Row will probably be cached and shared, so it must be read only.
+			writable: true,
 		}},
 	}
 	row.invalidateCount()
@@ -505,12 +504,15 @@ func (f *fragment) unprotectedSetBit(rowID, columnID uint64) (changed bool, err
 		return false, errors.Wrap(err, "incrementing")
 	}
 
-	// Get the row from row cache or fragment.storage.
-	row := f.unprotectedRow(rowID)
-	row.SetBit(columnID)
-
-	// Update the cache.
-	f.cache.Add(rowID, row.Count())
+	// If we're using a cache, update it. Otherwise skip the
+	// possibly-expensive count operation.
+	if f.CacheType != CacheTypeNone {
+		n := f.storage.CountRange(rowID*ShardWidth, (rowID+1)*ShardWidth)
+		f.cache.Add(rowID, n)
+	}
+	// Drop the rowCache entry; it's wrong, and we don't want to force
+	// a new copy if no one's reading it.
+	f.rowCache.Add(rowID, nil)
 
 	f.stats.Count("setBit", 1, 0.001)
 
@@ -566,12 +568,15 @@ func (f *fragment) unprotectedClearBit(rowID, columnID uint64) (changed bool, er
 		return false, errors.Wrap(err, "incrementing")
 	}
 
-	// Get the row from cache or fragment.storage.
-	row := f.unprotectedRow(rowID)
-	row.clearBit(columnID)
-
-	// Update the cache.
-	f.cache.Add(rowID, row.Count())
+	// If we're using a cache, update it. Otherwise skip the
+	// possibly-expensive count operation.
+	if f.CacheType != CacheTypeNone {
+		n := f.storage.CountRange(rowID*ShardWidth, (rowID+1)*ShardWidth)
+		f.cache.Add(rowID, n)
+	}
+	// Drop the rowCache entry; it's wrong, and we don't want to force
+	// a new copy if no one's reading it.
+	f.rowCache.Add(rowID, nil)
 
 	f.stats.Count("clearBit", 1, 1.0)
 
@@ -1849,9 +1854,7 @@ func (f *fragment) importPositions(set, clear []uint64, rowSet map[uint64]struct
 		f.cache.BulkAdd(rowID, n)
 
 		if smallWrite {
-			if _, ok := f.rowCache.Fetch(rowID); ok { // we won't update the rowCache if it wasn't already in there.
-				f.rowCache.Add(rowID, f.rowFromStorage(rowID))
-			}
+			f.rowCache.Add(rowID, nil)
 		}
 	}
 
diff --git a/roaring/btree.go b/roaring/btree.go
index 192993c3..53489af8 100644
--- a/roaring/btree.go
+++ b/roaring/btree.go
@@ -570,6 +570,13 @@ func (t *tree) Set(k uint64, v *Container) {
 	//defer func() {
 	//	dbg("--- POST\n%s\n====\n", t.dump())
 	//}()
+	// we don't want to store nil containers; if you try to set a
+	// container to nil, that's equivalent to not having one at that
+	// location.
+	if v == nil {
+		_ = t.Delete(k)
+		return
+	}
 
 	pi := -1
 	var p *x
@@ -642,7 +649,9 @@ func (t *tree) Put(k uint64, upd func(oldV *Container, exists bool) (newV *Conta
 		if !written {
 			return
 		}
-
+		if newV == nil {
+			return
+		}
 		z := t.insert(btDPool.Get().(*d), 0, k, newV)
 		t.r, t.first, t.last = z, z, z
 		return
@@ -667,7 +676,11 @@ func (t *tree) Put(k uint64, upd func(oldV *Container, exists bool) (newV *Conta
 				if !written {
 					return
 				}
-
+				// delete nil containers rather than storing them.
+				if newV == nil {
+					t.Delete(k)
+					return
+				}
 				x.d[i].v = newV
 			}
 			return
@@ -686,6 +699,10 @@ func (t *tree) Put(k uint64, upd func(oldV *Container, exists bool) (newV *Conta
 			if !written {
 				return
 			}
+			// nil values don't need to exist, and break iteration later.
+			if newV == nil {
+				return
+			}
 
 			switch {
 			case x.c < 2*kd:
@@ -876,6 +893,46 @@ func (e *enumerator) Next() (k uint64, v *Container, err error) {
 	return k, v, err
 }
 
+// Every iterates over a tree.
+func (e *enumerator) Every(upd func(oldV *Container, exists bool) (newV *Container, write bool)) error {
+	if err := e.err; err != nil {
+		return err
+	}
+
+	if e.ver != e.t.ver {
+		f, _ := e.t.Seek(e.k)
+		*e = *f
+		f.Close()
+	}
+
+	for {
+		if e.q == nil {
+			e.err = io.EOF
+			return e.err
+		}
+
+		if e.i >= e.q.c {
+			if err := e.next(); err != nil {
+				e.err = err
+				return e.err
+			}
+		}
+
+		i := e.q.d[e.i]
+		nv, write := upd(i.v, true)
+		if write {
+			if nv == nil {
+				e.t.Delete(e.q.d[e.i].k)
+			} else {
+				e.q.d[e.i].v = nv
+			}
+		}
+		// Any error returned would be stashed in e.err, and would come up
+		// on the next call.
+		_ = e.next()
+	}
+}
+
 func (e *enumerator) next() error {
 	if e.q == nil {
 		e.err = io.EOF
diff --git a/roaring/container_stash.go b/roaring/container_stash.go
index 728730d6..46725238 100644
--- a/roaring/container_stash.go
+++ b/roaring/container_stash.go
@@ -15,6 +15,7 @@
 package roaring
 
 import (
+	"fmt"
 	"reflect"
 	"runtime"
 	"unsafe"
@@ -39,24 +40,84 @@ type Container struct {
 	pointer  *uint16                  // the data pointer
 	len, cap int32                    // length and cap
 	n        int32                    // number of integers in container
-	mapped   bool                     // mapped directly to a byte slice when true
-	typ      byte                     // array, bitmap, or run
+	flags    containerFlags           // internal flags
+	typeID   byte                     // array, bitmap, or run
 	data     [stashedArraySize]uint16 // immediate data for small arrays or runs
 }
 
+type containerFlags uint8
+
+const (
+	flagMapped = containerFlags(1 << iota)
+	flagFrozen
+)
+
+func (c *Container) String() string {
+	if c == nil {
+		return "<nil container>"
+	}
+	froze := ""
+	switch c.flags {
+	case flagFrozen:
+		froze = "frozen "
+	case flagMapped:
+		froze = "mapped "
+	case flagFrozen | flagMapped:
+		froze = "frozen/mapped"
+	}
+	switch c.typeID {
+	case containerArray:
+		return fmt.Sprintf("<%sarray container, N=%d>", froze, c.N())
+	case containerBitmap:
+		return fmt.Sprintf("<%sbitmap container, N=%d, len %dx uint64>",
+			froze, c.N(), len(c.bitmap()))
+	case containerRun:
+		return fmt.Sprintf("<%srun container, N=%d, len %dx interval>",
+			froze, c.N(), len(c.runs()))
+	default:
+		return fmt.Sprintf("<unknown %s%d container, N=%d>", froze, c.typeID, c.N())
+	}
+}
+
 // NewContainer returns a new instance of container. This trivial function
 // may later become more interesting.
 func NewContainer() *Container {
 	statsHit("NewContainer")
-	c := &Container{typ: containerArray, len: 0, cap: stashedArraySize}
+	c := &Container{typeID: containerArray, len: 0, cap: stashedArraySize}
 	c.pointer = (*uint16)(unsafe.Pointer(&c.data[0]))
 	return c
 }
 
 // NewContainerBitmap makes a bitmap container using the provided bitmap, or
 // an empty one if provided bitmap is nil. If the provided bitmap is too short,
-// it will be padded.
-func NewContainerBitmap(n int32, bitmap []uint64) *Container {
+// it will be padded. This function's API is wrong; it should have been
+// written as NewContainerBitmapN, and this should not take the n argument,
+// but I did it wrong initially and now that would be a breaking change.
+func NewContainerBitmap(n int, bitmap []uint64) *Container {
+	if bitmap == nil {
+		return NewContainerBitmapN(nil, 0)
+	}
+	// pad to required length
+	if len(bitmap) < bitmapN {
+		bm2 := make([]uint64, bitmapN)
+		copy(bm2, bitmap)
+		bitmap = bm2
+	}
+	c := &Container{typeID: containerBitmap}
+	c.setBitmap(bitmap)
+	// set n based on bitmap contents.
+	if n < 0 {
+		c.bitmapRepair()
+	} else {
+		c.setN(int32(n))
+	}
+	return c
+}
+
+// NewContainerBitmapN makes a bitmap container using the provided bitmap, or
+// an empty one if provided bitmap is nil. If the provided bitmap is too short,
+// it will be padded. The container's count is specified directly.
+func NewContainerBitmapN(bitmap []uint64, n int32) *Container {
 	if bitmap == nil {
 		bitmap = make([]uint64, bitmapN)
 	}
@@ -66,23 +127,40 @@ func NewContainerBitmap(n int32, bitmap []uint64) *Container {
 		copy(bm2, bitmap)
 		bitmap = bm2
 	}
-	c := &Container{typ: containerBitmap, n: n}
+	c := &Container{typeID: containerBitmap, n: n}
 	c.setBitmap(bitmap)
 	return c
 }
 
-// NewContainerArray returns an array using the provided set of values. It's
-// okay if the slice is nil; that's a length of zero.
+// NewContainerArray returns an array container using the provided set of
+// values. It's okay if the slice is nil; that's a length of zero.
 func NewContainerArray(set []uint16) *Container {
-	c := &Container{typ: containerArray, n: int32(len(set))}
+	c := &Container{typeID: containerArray, n: int32(len(set))}
 	c.setArray(set)
 	return c
 }
 
-// NewContainerRun creates a new run array using a provided (possibly nil)
+// NewContainerArrayCopy returns an array container using the provided set of
+// values. It's okay if the slice is nil; that's a length of zero. It copies
+// the provided slice to new storage.
+func NewContainerArrayCopy(set []uint16) *Container {
+	c := &Container{typeID: containerArray, n: int32(len(set))}
+	c.setArrayMaybeCopy(set, true)
+	return c
+}
+
+// NewContainerArrayN returns an array container using the specified
+// set of values, but overriding n.
+func NewContainerArrayN(set []uint16, n int32) *Container {
+	c := &Container{typeID: containerArray, n: n}
+	c.setArray(set)
+	return c
+}
+
+// NewContainerRun creates a new run container using a provided (possibly nil)
 // slice of intervals.
 func NewContainerRun(set []interval16) *Container {
-	c := &Container{typ: containerRun}
+	c := &Container{typeID: containerRun}
 	c.setRuns(set)
 	for _, run := range set {
 		c.n += int32(run.last-run.start) + 1
@@ -90,61 +168,242 @@ func NewContainerRun(set []interval16) *Container {
 	return c
 }
 
+// NewContainerRunCopy creates a new run container using a provided (possibly nil)
+// slice of intervals. It copies the provided slice to new storage.
+func NewContainerRunCopy(set []interval16) *Container {
+	c := &Container{typeID: containerRun}
+	c.setRunsMaybeCopy(set, true)
+	for _, run := range set {
+		c.n += int32(run.last-run.start) + 1
+	}
+	return c
+}
+
+// NewContainerRunN creates a new run array using a provided (possibly nil)
+// slice of intervals. It overrides n using the provided value.
+func NewContainerRunN(set []interval16, n int32) *Container {
+	c := &Container{typeID: containerRun, n: n}
+	c.setRuns(set)
+	return c
+}
+
 // Mapped returns the internal mapped field, which indicates whether the
 // slice's backing store is believed to be associated with unwriteable
 // mmapped space.
 func (c *Container) Mapped() bool {
-	return c.mapped
+	if c == nil {
+		return false
+	}
+	return (c.flags & flagMapped) != 0
 }
 
-// N returns the internal n field.
+// frozen() returns the internal frozen state. It isn't exported because
+// nothing outside this package should be thinking about this.
+func (c *Container) frozen() bool {
+	if c == nil {
+		return true
+	}
+	return (c.flags & flagFrozen) != 0
+}
+
+// N returns the 1-count of the container.
 func (c *Container) N() int32 {
+	if c == nil {
+		return 0
+	}
 	return c.n
 }
 
+func (c *Container) setN(n int32) {
+	if c == nil {
+		if roaringParanoia {
+			panic("trying to setN on a nil container")
+		}
+		return
+	}
+	c.n = n
+}
+
+func (c *Container) typ() byte {
+	if c == nil {
+		return containerNil
+	}
+	return c.typeID
+}
+
+// setTyp should only be called if you already know that c is a
+// non-nil, non-frozen, container.
+func (c *Container) setTyp(newType byte) {
+	if roaringParanoia {
+		if c == nil || c.frozen() {
+			panic("setTyp on nil or frozen container")
+		}
+	}
+	c.typeID = newType
+}
+
+func (c *Container) setMapped(mapped bool) {
+	if roaringParanoia {
+		if c == nil || c.frozen() {
+			panic("setMapped on nil or frozen container")
+		}
+	}
+	if mapped {
+		c.flags |= flagMapped
+	} else {
+		c.flags &^= flagMapped
+	}
+}
+
+// Freeze returns an unmodifiable container identical to c. This might
+// be c, now marked unmodifiable, or might be a new container.
+func (c *Container) Freeze() *Container {
+	if c == nil {
+		return nil
+	}
+	c.flags |= flagFrozen
+	return c
+}
+
+// Thaw returns a modifiable container identical to c. This may be c, or it
+// may be a new container with distinct backing store.
+func (c *Container) Thaw() *Container {
+	if roaringParanoia {
+		if c == nil {
+			panic("trying to thaw a nil container")
+		}
+	}
+	if c.flags&(flagFrozen|flagMapped) == 0 {
+		return c
+	}
+	return c.unmapOrClone()
+}
+
+func (c *Container) unmapOrClone() *Container {
+	if c.flags&flagFrozen != 0 {
+		// Caqn't modify this container, therefore, we have to make a
+		// copy.
+		return c.Clone()
+	}
+	c.flags &^= flagMapped
+	// mapped: we want to unmap the storage.
+	switch c.typeID {
+	case containerArray:
+		// mapped flag is wrong here
+		if c.pointer == (*uint16)(unsafe.Pointer(&c.data)) {
+			return c
+		}
+		// maybe it fits in storage
+		if c.len <= stashedArraySize {
+			copy(c.data[:stashedArraySize], c.array())
+			c.pointer, c.cap = (*uint16)(unsafe.Pointer(&c.data)), stashedArraySize
+			return c
+		}
+		array := c.array()
+		tmp := make([]uint16, c.len)
+		copy(tmp, array)
+		h := (*reflect.SliceHeader)(unsafe.Pointer(&tmp))
+		c.pointer, c.cap = (*uint16)(unsafe.Pointer(h.Data)), int32(h.Cap)
+		runtime.KeepAlive(&tmp)
+	case containerRun:
+		// mapped flag is wrong here
+		if c.pointer == (*uint16)(unsafe.Pointer(&c.data)) {
+			return c
+		}
+		oldRuns := c.runs()
+		// maybe it fits in storage
+		if c.len <= stashedRunSize {
+			c.pointer, c.cap = (*uint16)(unsafe.Pointer(&c.data)), stashedRunSize
+			copy(c.runs(), oldRuns)
+			return c
+		}
+		tmp := make([]interval16, c.len)
+		copy(tmp, oldRuns)
+		h := (*reflect.SliceHeader)(unsafe.Pointer(&tmp))
+		c.pointer, c.cap = (*uint16)(unsafe.Pointer(h.Data)), int32(h.Cap)
+		runtime.KeepAlive(&tmp)
+	case containerBitmap:
+		bitmap := c.bitmap()
+		tmp := make([]uint64, bitmapN)
+		copy(tmp, bitmap)
+		h := (*reflect.SliceHeader)(unsafe.Pointer(&tmp))
+		c.pointer, c.len, c.cap = (*uint16)(unsafe.Pointer(h.Data)), bitmapN, bitmapN
+		runtime.KeepAlive(&tmp)
+	default:
+		panic(fmt.Sprintf("can't thaw invalid container, type %d", c.typeID))
+	}
+	return c
+}
+
 // array yields the data viewed as a slice of uint16 values.
 func (c *Container) array() []uint16 {
 	if roaringParanoia {
-		if c.typ != containerArray {
+		if c == nil {
+			panic("attempt to read a nil container's array")
+		}
+		if c.typeID != containerArray {
 			panic("attempt to read non-array's array")
 		}
 	}
 	return *(*[]uint16)(unsafe.Pointer(&reflect.SliceHeader{Data: uintptr(unsafe.Pointer(c.pointer)), Len: int(c.len), Cap: int(c.cap)}))
 }
 
-// setArray stores a set of uint16s as data.
-func (c *Container) setArray(array []uint16) {
+// setArrayMaybeCopy stores a set of uint16s as data. c must not be frozen.
+// If doCopy is set, it will ensure that the data get copied (possibly to
+// its internal stash.)
+func (c *Container) setArrayMaybeCopy(array []uint16, doCopy bool) {
 	if roaringParanoia {
-		if c.typ != containerArray {
+		if c == nil || c.frozen() {
+			panic("setArray on nil or frozen container")
+		}
+		if c.typeID != containerArray {
 			panic("attempt to write non-array's array")
 		}
 	}
 	// no array: start with our default 5-value array
 	if array == nil {
 		c.pointer, c.len, c.cap = (*uint16)(unsafe.Pointer(&c.data[0])), 0, stashedArraySize
+		c.n = c.len
 		return
 	}
 	h := (*reflect.SliceHeader)(unsafe.Pointer(&array))
 	if h.Data == uintptr(unsafe.Pointer(c.pointer)) {
 		// nothing to do but update length
 		c.len = int32(h.Len)
+		c.n = c.len
 		return
 	}
 	// array we can fit in data store:
 	if len(array) <= stashedArraySize {
 		copy(c.data[:stashedArraySize], array)
 		c.pointer, c.len, c.cap = (*uint16)(unsafe.Pointer(&c.data[0])), int32(len(array)), stashedArraySize
-		c.mapped = false // this is no longer using a hypothetical mmapped input array
+		c.n = c.len
+		c.flags &^= flagMapped // this is no longer using a hypothetical mmapped input array
 		return
 	}
+	// copy the array
+	if doCopy {
+		a2 := make([]uint16, len(array))
+		copy(a2, array)
+		h = (*reflect.SliceHeader)(unsafe.Pointer(&a2))
+	}
 	c.pointer, c.len, c.cap = (*uint16)(unsafe.Pointer(h.Data)), int32(h.Len), int32(h.Cap)
+	c.n = c.len
 	runtime.KeepAlive(&array)
 }
 
+// setArrayMaybeCopy stores a set of uint16s as data. c must not be frozen.
+func (c *Container) setArray(array []uint16) {
+	c.setArrayMaybeCopy(array, false)
+}
+
 // bitmap yields the data viewed as a slice of uint64s holding bits.
 func (c *Container) bitmap() []uint64 {
 	if roaringParanoia {
-		if c.typ != containerBitmap {
+		if c == nil {
+			panic("attempt to read nil container's bitmap")
+		}
+		if c.typeID != containerBitmap {
 			panic("attempt to read non-bitmap's bitmap")
 		}
 	}
@@ -153,8 +412,11 @@ func (c *Container) bitmap() []uint64 {
 
 // setBitmap stores a set of uint64s as data.
 func (c *Container) setBitmap(bitmap []uint64) {
+	if c == nil || c.frozen() {
+		panic("setBitmap on nil or frozen container")
+	}
 	if roaringParanoia {
-		if c.typ != containerBitmap {
+		if c.typeID != containerBitmap {
 			panic("attempt to write non-bitmap's bitmap")
 		}
 	}
@@ -166,17 +428,29 @@ func (c *Container) setBitmap(bitmap []uint64) {
 // runs yields the data viewed as a slice of intervals.
 func (c *Container) runs() []interval16 {
 	if roaringParanoia {
-		if c.typ != containerRun {
+		if c == nil {
+			panic("attempt to read nil container's runs")
+		}
+		if c.typeID != containerRun {
 			panic("attempt to read non-run's runs")
 		}
 	}
 	return *(*[]interval16)(unsafe.Pointer(&reflect.SliceHeader{Data: uintptr(unsafe.Pointer(c.pointer)), Len: int(c.len), Cap: int(c.cap)}))
 }
 
-// setRuns stores a set of intervals as data.
+// setRuns stores a set of intervals as data. c must not be frozen.
 func (c *Container) setRuns(runs []interval16) {
+	c.setRunsMaybeCopy(runs, false)
+}
+
+// setRunsMaybeCopy stores a set of intervals as data. c must not be frozen.
+// If doCopy is set, the values will be copied to different storage.
+func (c *Container) setRunsMaybeCopy(runs []interval16, doCopy bool) {
 	if roaringParanoia {
-		if c.typ != containerRun {
+		if c == nil || c.frozen() {
+			panic("setRuns on nil or frozen container")
+		}
+		if c.typeID != containerRun {
 			panic("attempt to write non-run's runs")
 		}
 	}
@@ -197,20 +471,64 @@ func (c *Container) setRuns(runs []interval16) {
 		newRuns := *(*[]interval16)(unsafe.Pointer(&reflect.SliceHeader{Data: uintptr(unsafe.Pointer(&c.data[0])), Len: stashedRunSize, Cap: stashedRunSize}))
 		copy(newRuns, runs)
 		c.pointer, c.len, c.cap = (*uint16)(unsafe.Pointer(&c.data[0])), int32(len(runs)), stashedRunSize
-		c.mapped = false // this is no longer using a hypothetical mmapped input array
+		c.flags &^= flagMapped // this is no longer using a hypothetical mmapped input array
 		return
 	}
+	if doCopy {
+		r2 := make([]interval16, len(runs))
+		copy(r2, runs)
+		h = (*reflect.SliceHeader)(unsafe.Pointer(&r2))
+	}
 	c.pointer, c.len, c.cap = (*uint16)(unsafe.Pointer(h.Data)), int32(h.Len), int32(h.Cap)
 	runtime.KeepAlive(&runs)
 }
 
-// Update updates the container
+// UpdateOrMake updates the container, yielding a new container if necessary.
+func (c *Container) UpdateOrMake(typ byte, n int32, mapped bool) *Container {
+	if c == nil {
+		switch typ {
+		case containerRun:
+			c = NewContainerRunN(nil, n)
+		case containerBitmap:
+			c = NewContainerBitmapN(nil, n)
+		default:
+			c = NewContainerArrayN(nil, n)
+		}
+		c.flags |= flagMapped
+		return c
+	}
+	// ensure that we are allowed to modify this container
+	c = c.Thaw()
+	c.typeID = typ
+	c.n = n
+	// note: this probably shouldn't be happening, the decision should be getting
+	// made when we specify the storage.
+	c.setMapped(mapped)
+	// we don't know that any existing slice is usable, so let's ditch it
+	switch c.typeID {
+	case containerArray:
+		c.pointer, c.len, c.cap = (*uint16)(unsafe.Pointer(&c.data[0])), int32(0), stashedArraySize
+	case containerRun:
+		c.pointer, c.len, c.cap = (*uint16)(unsafe.Pointer(&c.data[0])), 0, stashedRunSize
+	default:
+		c.pointer, c.len, c.cap = nil, 0, 0
+	}
+	return c
+}
+
+// Update updates the container if possible. It is an error to
+// call Update on a frozen container.
 func (c *Container) Update(typ byte, n int32, mapped bool) {
-	c.typ = typ
+	if c == nil || c.frozen() {
+		panic("cannot Update a nil or frozen container")
+	}
+	c.typeID = typ
 	c.n = n
-	c.mapped = mapped
+	// note: this probably shouldn't be happening, the decision should be getting
+	// made when we specify the storage.
+	c.setMapped(mapped)
 	// we don't know that any existing slice is usable, so let's ditch it
-	switch c.typ {
+	switch c.typeID {
 	case containerArray:
 		c.pointer, c.len, c.cap = (*uint16)(unsafe.Pointer(&c.data[0])), int32(0), stashedArraySize
 	case containerRun:
@@ -222,56 +540,30 @@ func (c *Container) Update(typ byte, n int32, mapped bool) {
 
 // isArray returns true if the container is an array container.
 func (c *Container) isArray() bool {
-	return c.typ == containerArray
+	if roaringParanoia {
+		if c == nil {
+			panic("calling isArray on nil container")
+		}
+	}
+	return c.typeID == containerArray
 }
 
 // isBitmap returns true if the container is a bitmap container.
 func (c *Container) isBitmap() bool {
-	return c.typ == containerBitmap
+	if roaringParanoia {
+		if c == nil {
+			panic("calling isBitmap on nil container")
+		}
+	}
+	return c.typeID == containerBitmap
 }
 
 // isRun returns true if the container is a run-length-encoded container.
 func (c *Container) isRun() bool {
-	return c.typ == containerRun
-}
-
-// unmapArray ensures that the container is not using mmapped storage.
-func (c *Container) unmapArray() {
-	if !c.mapped {
-		return
-	}
-	array := c.array()
-	tmp := make([]uint16, c.len)
-	copy(tmp, array)
-	h := (*reflect.SliceHeader)(unsafe.Pointer(&tmp))
-	c.pointer, c.cap = (*uint16)(unsafe.Pointer(h.Data)), int32(h.Cap)
-	runtime.KeepAlive(&tmp)
-	c.mapped = false
-}
-
-// unmapBitmap ensures that the container is not using mmapped storage.
-func (c *Container) unmapBitmap() {
-	if !c.mapped {
-		return
-	}
-	bitmap := c.bitmap()
-	tmp := make([]uint64, c.len)
-	copy(tmp, bitmap)
-	h := (*reflect.SliceHeader)(unsafe.Pointer(&tmp))
-	c.pointer, c.cap = (*uint16)(unsafe.Pointer(h.Data)), int32(h.Cap)
-	runtime.KeepAlive(&tmp)
-	c.mapped = false
-}
-
-// unmapRun ensures that the container is not using mmapped storage.
-func (c *Container) unmapRun() {
-	if !c.mapped {
-		return
+	if roaringParanoia {
+		if c == nil {
+			panic("calling isRun on nil container")
+		}
 	}
-	runs := c.runs()
-	tmp := make([]interval16, c.len)
-	copy(tmp, runs)
-	h := (*reflect.SliceHeader)(unsafe.Pointer(&tmp))
-	c.pointer, c.cap = (*uint16)(unsafe.Pointer(h.Data)), int32(h.Cap)
-	c.mapped = false
+	return c.typeID == containerRun
 }
diff --git a/roaring/containers_btree.go b/roaring/containers_btree.go
index 5934a124..c2dbc01f 100644
--- a/roaring/containers_btree.go
+++ b/roaring/containers_btree.go
@@ -15,6 +15,7 @@
 package roaring
 
 import (
+	"fmt"
 	"io"
 )
 
@@ -42,7 +43,7 @@ func NewBTreeBitmap(a ...uint64) *Bitmap {
 
 func (btc *bTreeContainers) Get(key uint64) *Container {
 	// Check the last* cache for same container.
-	if key == btc.lastKey && btc.lastContainer != nil {
+	if key == btc.lastKey {
 		return btc.lastContainer
 	}
 
@@ -57,11 +58,15 @@ func (btc *bTreeContainers) Get(key uint64) *Container {
 }
 
 func (btc *bTreeContainers) Put(key uint64, c *Container) {
+	// If we don't do this, a Put on a container we just got from
+	// Get can result in the tree containing a different container
+	// than we'll get on next lookup.
+	btc.lastKey, btc.lastContainer = key, c
 	// If a mapped container is added to the tree, reset the
 	// lastContainer cache so that the cache is not pointing
 	// at a read-only mmap.
 	if c.Mapped() {
-		btc.lastContainer = nil
+		btc.lastKey = ^uint64(0)
 	}
 	btc.tree.Set(key, c)
 }
@@ -69,13 +74,13 @@ func (btc *bTreeContainers) Put(key uint64, c *Container) {
 func (u updater) update(oldV *Container, exists bool) (*Container, bool) {
 	// update the existing container
 	if exists {
-		oldV.Update(u.typ, u.n, u.mapped)
-		return oldV, false
+		oldV = oldV.UpdateOrMake(u.typ, u.n, u.mapped)
+		return oldV, true
 	}
 	cont := NewContainer()
-	cont.typ = u.typ
-	cont.n = u.n
-	cont.mapped = u.mapped
+	cont.setTyp(u.typ)
+	cont.setN(u.n)
+	cont.setMapped(u.mapped)
 	return cont, true
 }
 
@@ -98,7 +103,7 @@ func (btc *bTreeContainers) Remove(key uint64) {
 
 func (btc *bTreeContainers) GetOrCreate(key uint64) *Container {
 	// Check the last* cache for same container.
-	if key == btc.lastKey && btc.lastContainer != nil {
+	if key == btc.lastKey {
 		return btc.lastContainer
 	}
 
@@ -119,7 +124,7 @@ func (btc *bTreeContainers) Count() (n uint64) {
 	e, _ := btc.tree.Seek(0)
 	_, c, err := e.Next()
 	for err != io.EOF {
-		n += uint64(c.n)
+		n += uint64(c.N())
 		_, c, err = e.Next()
 	}
 	return n
@@ -142,6 +147,23 @@ func (btc *bTreeContainers) Clone() Containers {
 	return nbtc
 }
 
+func (btc *bTreeContainers) Freeze() Containers {
+	nbtc := newBTreeContainers()
+
+	itr, err := btc.tree.SeekFirst()
+	if err == io.EOF {
+		return nbtc
+	}
+	for {
+		k, v, err := itr.Next()
+		if err == io.EOF {
+			break
+		}
+		nbtc.tree.Set(k, v.Freeze())
+	}
+	return nbtc
+}
+
 func (btc *bTreeContainers) Last() (key uint64, c *Container) {
 	if btc.tree.Len() == 0 {
 		return 0, nil
@@ -156,7 +178,10 @@ func (btc *bTreeContainers) Size() int {
 
 func (btc *bTreeContainers) Reset() {
 	btc.tree = treeNew()
-	btc.lastKey = 0
+	// use a definitely-invalid key, so we can distinguish between "you
+	// just looked that up, and it was a nil container" and "you have
+	// never looked that up before."
+	btc.lastKey = ^uint64(0)
 	btc.lastContainer = nil
 }
 
@@ -180,6 +205,23 @@ func (btc *bTreeContainers) Repair() {
 	}
 }
 
+// Update calls fn (existing-container, existed), and expects
+// (new-container, write). If write is true, the container is used to
+// replace the given container.
+func (btc *bTreeContainers) Update(key uint64, fn func(*Container, bool) (*Container, bool)) {
+	btc.tree.Put(key, fn)
+}
+
+// UpdateEvery calls fn (existing-container, existed), and expects
+// (new-container, write). If write is true, the container is used to
+// replace the given container.
+func (btc *bTreeContainers) UpdateEvery(fn func(*Container, bool) (*Container, bool)) {
+	e, _ := btc.tree.Seek(0)
+	// currently not handling the error from this, but in practice it has
+	// to be io.EOF.
+	_ = e.Every(fn)
+}
+
 type btcIterator struct {
 	e   *enumerator
 	key uint64
@@ -187,19 +229,20 @@ type btcIterator struct {
 }
 
 func (i *btcIterator) Next() bool {
-
 	k, v, err := i.e.Next()
 	if err == io.EOF {
 		return false
 	}
+	if roaringParanoia {
+		if v == nil {
+			panic(fmt.Sprintf("got nil container for key %d", k))
+		}
+	}
 	i.key = k
 	i.val = v
 	return true
 }
 
 func (i *btcIterator) Value() (uint64, *Container) {
-	if i.val == nil {
-		return 0, nil
-	}
 	return i.key, i.val
 }
diff --git a/roaring/containers.go b/roaring/containers_slice.go
similarity index 64%
rename from roaring/containers.go
rename to roaring/containers_slice.go
index dc5d4118..cbff4f17 100644
--- a/roaring/containers.go
+++ b/roaring/containers_slice.go
@@ -50,15 +50,21 @@ func (sc *sliceContainers) PutContainerValues(key uint64, typ byte, n int, mappe
 	i := search64(sc.keys, key)
 	if i < 0 {
 		c := NewContainer()
-		c.typ = typ
-		c.n = int32(n)
-		c.mapped = mapped
+		c.setTyp(typ)
+		c.setN(int32(n))
+		c.setMapped(mapped)
 		sc.insertAt(key, c, -i-1)
 	} else {
-		c := sc.containers[i]
-		c.typ = typ
-		c.n = int32(n)
-		c.mapped = mapped
+		// if the container already exists, and is frozen, this may
+		// result in copying its data, which is sort of pointless
+		// because PutContainerValues almost always gets called
+		// because we're reading new data from a file -- but also
+		// that means this case probably never happens.
+		c := sc.containers[i].Thaw()
+		c.setTyp(typ)
+		c.setN(int32(n))
+		c.setMapped(mapped)
+		sc.containers[i] = c
 	}
 
 }
@@ -114,6 +120,17 @@ func (sc *sliceContainers) Clone() Containers {
 	return other
 }
 
+func (sc *sliceContainers) Freeze() Containers {
+	other := newSliceContainers()
+	other.keys = make([]uint64, len(sc.keys))
+	other.containers = make([]*Container, len(sc.containers))
+	copy(other.keys, sc.keys)
+	for i, c := range sc.containers {
+		other.containers[i] = c.Freeze()
+	}
+	return other
+}
+
 func (sc *sliceContainers) Last() (key uint64, c *Container) {
 	if len(sc.keys) == 0 {
 		return 0, nil
@@ -129,7 +146,7 @@ func (sc *sliceContainers) Size() int {
 func (sc *sliceContainers) Count() uint64 {
 	n := uint64(0)
 	for i := range sc.containers {
-		n += uint64(sc.containers[i].n)
+		n += uint64(sc.containers[i].N())
 	}
 	return n
 }
@@ -162,6 +179,42 @@ func (sc *sliceContainers) Repair() {
 	}
 }
 
+// Update calls fn (existing-container, existed), and expects
+// (new-container, write). If write is true, the container is used to
+// replace the given container.
+func (sc *sliceContainers) Update(key uint64, fn func(*Container, bool) (*Container, bool)) {
+	i, found := sc.seek(key)
+	var nc *Container
+	var write bool
+	if found {
+		nc, write = fn(sc.containers[i], true)
+		if write {
+			sc.containers[i] = nc
+		}
+	} else {
+		nc, write = fn(nil, false)
+		// don't expand the slice just to add a nil container, we
+		// could return that anyway
+		if write && nc != nil {
+			sc.containers = append(sc.containers, nil)
+			copy(sc.containers[i+1:], sc.containers[i:])
+			sc.containers[i] = nc
+		}
+	}
+}
+
+// UpdateEvery calls fn (existing-container, existed), and expects
+// (new-container, write). If write is true, the container is used to
+// replace the given container.
+func (sc *sliceContainers) UpdateEvery(fn func(*Container, bool) (*Container, bool)) {
+	for i, c := range sc.containers {
+		nc, write := fn(c, true)
+		if write {
+			sc.containers[i] = nc
+		}
+	}
+}
+
 type sliceIterator struct {
 	e     *sliceContainers
 	i     int
@@ -170,14 +223,20 @@ type sliceIterator struct {
 }
 
 func (si *sliceIterator) Next() bool {
-	if si.e == nil || si.i > len(si.e.keys)-1 {
+	if si.e == nil {
 		return false
 	}
-	si.key = si.e.keys[si.i]
-	si.value = si.e.containers[si.i]
-	si.i++
-
-	return true
+	// discard nil containers from iteration. we don't always
+	// actually remove them because copying is expensive.
+	for si.i < len(si.e.keys) {
+		si.key = si.e.keys[si.i]
+		si.value = si.e.containers[si.i]
+		si.i++
+		if si.value != nil {
+			return true
+		}
+	}
+	return false
 }
 
 func (si *sliceIterator) Value() (uint64, *Container) {
diff --git a/roaring/roaring.go b/roaring/roaring.go
index 2d1a2d08..cd7833a7 100644
--- a/roaring/roaring.go
+++ b/roaring/roaring.go
@@ -62,9 +62,10 @@ const (
 )
 
 const (
-	containerArray  byte = iota + 1 // slice of bit position values
-	containerBitmap                 // slice of 1024 uint64s
-	containerRun                    // container of run-encoded bits
+	containerNil    byte = iota // no container
+	containerArray              // slice of bit position values
+	containerBitmap             // slice of 1024 uint64s
+	containerRun                // container of run-encoded bits
 )
 
 // map used for a more descriptive print
@@ -74,6 +75,8 @@ var containerTypeNames = map[byte]string{
 	containerRun:    "run",
 }
 
+var fullContainer = NewContainerRun([]interval16{{start: 0, last: maxContainerVal}}).Freeze()
+
 type Containers interface {
 	// Get returns nil if the key does not exist.
 	Get(key uint64) *Container
@@ -95,12 +98,27 @@ type Containers interface {
 	// Clone does a deep copy of Containers, including cloning all containers contained.
 	Clone() Containers
 
+	// Freeze creates a shallow copy of Containers, freezing all the containers
+	// contained. The new copy is a distinct Containers, but the individual containers
+	// are shared (but marked as frozen).
+	Freeze() Containers
+
 	// Last returns the highest key and associated container.
 	Last() (key uint64, c *Container)
 
 	// Size returns the number of containers stored.
 	Size() int
 
+	// Update calls fn (existing-container, existed), and expects
+	// (new-container, write). If write is true, the container is used to
+	// replace the given container.
+	Update(key uint64, fn func(*Container, bool) (*Container, bool))
+
+	// UpdateEvery calls fn (existing-container, existed), and expects
+	// (new-container, write). If write is true, the container is used to
+	// replace the given container.
+	UpdateEvery(fn func(*Container, bool) (*Container, bool))
+
 	// Iterator returns a Contiterator which after a call to Next(), a call to Value() will
 	// return the first container at or after key. found will be true if a
 	// container is found at key.
@@ -149,6 +167,21 @@ func NewBitmap(a ...uint64) *Bitmap {
 	return b
 }
 
+// NewSliceBitmap makes a new bitmap, explicitly selecting the slice containers
+// type, which performs better in cases where we expect a contiguous block of
+// containers added in ascending order, such as when extracting a range from
+// another bitmap.
+func NewSliceBitmap(a ...uint64) *Bitmap {
+	b := &Bitmap{
+		Containers: newSliceContainers(),
+	}
+	// TODO: We have no way to report this. We aren't in a server context
+	// so we haven't got a logger, nothing is checking for nil returns
+	// from this...
+	_, _ = b.AddN(a...)
+	return b
+}
+
 // NewFileBitmap returns a Bitmap with an initial set of values, used for file storage.
 // By default, this is a copy of NewBitmap, but is replaced with B+Tree in server/enterprise.go
 var NewFileBitmap func(a ...uint64) *Bitmap = NewBTreeBitmap
@@ -168,6 +201,23 @@ func (b *Bitmap) Clone() *Bitmap {
 	return other
 }
 
+// Freeze returns a shallow copy of the bitmap. The new bitmap
+// is a distinct bitmap, with a new Containers object, but the
+// actual containers it holds are the same as the parent's
+// containers, but have been frozen.
+func (b *Bitmap) Freeze() *Bitmap {
+	if b == nil {
+		return nil
+	}
+
+	// Create a copy of the bitmap structure.
+	other := &Bitmap{
+		Containers: b.Containers.Freeze(),
+	}
+
+	return other
+}
+
 // Add adds values to the bitmap. TODO(2.0) deprecate - use the more general
 // AddN (though be aware that it modifies 'a' in place).
 func (b *Bitmap) Add(a ...uint64) (changed bool, err error) {
@@ -235,7 +285,7 @@ func (b *Bitmap) DirectRemoveN(a ...uint64) (changed int) {
 // container level operation across a list of values and return the number of
 // trues while modifying the list of values in place to contain the
 // true-returning values in order.
-func (b *Bitmap) directOpN(op func(c *Container, v uint16) bool, a ...uint64) (changed int) {
+func (b *Bitmap) directOpN(op func(c *Container, v uint16) (*Container, bool), a ...uint64) (changed int) {
 	hb := uint64(0xFFFFFFFFFFFFFFFF) // impossible sentinel value
 	var cont *Container
 	for _, v := range a {
@@ -243,10 +293,15 @@ func (b *Bitmap) directOpN(op func(c *Container, v uint16) bool, a ...uint64) (c
 			hb = newhb
 			cont = b.Containers.GetOrCreate(hb)
 		}
-		if op(cont, lowbits(v)) {
+		newC, change := op(cont, lowbits(v))
+		if change {
 			a[changed] = v
 			changed++
 		}
+		if newC != cont {
+			b.Containers.Put(hb, newC)
+			cont = newC
+		}
 	}
 	return changed
 }
@@ -255,7 +310,11 @@ func (b *Bitmap) directOpN(op func(c *Container, v uint16) bool, a ...uint64) (c
 // deprecate in favor of DirectAddN.
 func (b *Bitmap) DirectAdd(v uint64) bool {
 	cont := b.Containers.GetOrCreate(highbits(v))
-	return cont.add(lowbits(v))
+	newC, changed := cont.add(lowbits(v))
+	if newC != cont {
+		b.Containers.Put(highbits(v), newC)
+	}
+	return changed
 }
 
 // Contains returns true if v is in the bitmap.
@@ -313,11 +372,11 @@ func (b *Bitmap) RemoveN(a ...uint64) (changed int, err error) {
 
 func (b *Bitmap) remove(v uint64) bool {
 	c := b.Containers.Get(highbits(v))
-	if c == nil {
-		return false
+	newC, changed := c.remove(lowbits(v))
+	if newC != c {
+		b.Containers.Put(highbits(v), newC)
 	}
-	// TODO - do nil check inside c.remove?
-	return c.remove(lowbits(v))
+	return changed
 }
 
 // Max returns the highest value in the bitmap.
@@ -345,7 +404,7 @@ func (b *Bitmap) Any() bool {
 	// container should be removed from the bitmap though.
 	for iter.Next() {
 		_, c := iter.Value()
-		if c.n > 0 {
+		if c.N() > 0 {
 			return true
 		}
 	}
@@ -359,7 +418,6 @@ func (b *Bitmap) Size() int {
 	for citer.Next() {
 		_, c := citer.Value()
 		numbytes += c.size()
-
 	}
 	return numbytes
 }
@@ -392,7 +450,7 @@ func (b *Bitmap) CountRange(start, end uint64) (n uint64) {
 			continue
 		}
 		if k < ekey {
-			n += uint64(c.n)
+			n += uint64(c.N())
 			continue
 		}
 		if k == ekey {
@@ -448,6 +506,8 @@ func (b *Bitmap) ForEachRange(start, end uint64, fn func(uint64)) {
 }
 
 // OffsetRange returns a new bitmap with a containers offset by start.
+// The containers themselves are shared, so they get frozen so it will
+// be safe to interact with them.
 func (b *Bitmap) OffsetRange(offset, start, end uint64) *Bitmap {
 	if lowbits(offset) != 0 {
 		panic("offset must not contain low bits")
@@ -462,13 +522,13 @@ func (b *Bitmap) OffsetRange(offset, start, end uint64) *Bitmap {
 	off := highbits(offset)
 	hi0, hi1 := highbits(start), highbits(end)
 	citer, _ := b.Containers.Iterator(hi0)
-	other := NewBitmap()
+	other := NewSliceBitmap()
 	for citer.Next() {
 		k, c := citer.Value()
 		if k >= hi1 {
 			break
 		}
-		other.Containers.Put(off+(k-hi0), c)
+		other.Containers.Put(off+(k-hi0), c.Freeze())
 	}
 	return other
 }
@@ -537,7 +597,10 @@ func (b *Bitmap) Union(others ...*Bitmap) *Bitmap {
 		b.unionIntoTargetSingle(output, others[0])
 		return output
 	}
-	output := b.Clone()
+	// It may seem counterintuitive to freeze this, but the result is
+	// a new bitmap which can be safely modified, but postponing any
+	// allocations until an actual write to any given container.
+	output := b.Freeze()
 	output.UnionInPlace(others...)
 	return output
 }
@@ -556,11 +619,11 @@ func (b *Bitmap) unionIntoTargetSingle(target *Bitmap, other *Bitmap) {
 	kj, cj := jiter.Value()
 	for i || j {
 		if i && (!j || ki < kj) {
-			target.Containers.Put(ki, ci.Clone())
+			target.Containers.Put(ki, ci.Freeze())
 			i = iiter.Next()
 			ki, ci = iiter.Value()
 		} else if j && (!i || ki > kj) {
-			target.Containers.Put(kj, cj.Clone())
+			target.Containers.Put(kj, cj.Freeze())
 			j = jiter.Next()
 			kj, cj = jiter.Value()
 		} else { // ki == kj
@@ -693,11 +756,11 @@ func (b *Bitmap) unionInPlace(others ...*Bitmap) {
 			tContainer := target.Containers.Get(iKey)
 			// if the target's full, short-circuit out.
 			if tContainer != nil {
-				if tContainer.n == maxContainerVal+1 {
+				if tContainer.N() == maxContainerVal+1 {
 					bitmapIters.markItersWithKeyAsHandled(i, iKey)
 					continue
 				}
-				expectedN = int64(tContainer.n)
+				expectedN = int64(tContainer.N())
 			}
 			// Check i and later iters for any max-range containers, and
 			// find out how many there are.
@@ -707,7 +770,7 @@ func (b *Bitmap) unionInPlace(others ...*Bitmap) {
 				// range that a container can store, so instead of calculating a
 				// union we can generate an RLE container that represents the entire
 				// range.
-				tContainer = NewContainerRun([]interval16{{start: 0, last: maxContainerVal}})
+				tContainer = fullContainer
 				target.Containers.Put(iKey, tContainer)
 				bitmapIters.markItersWithKeyAsHandled(i, iKey)
 				continue
@@ -722,9 +785,9 @@ func (b *Bitmap) unionInPlace(others ...*Bitmap) {
 				// No existing target container.
 				if summaryStats.c == 1 {
 					// There's no target and we have only one container, we
-					// can just clone it instead of unioning.
+					// can just reuse it instead of unioning.
 					statsHit("unionInPlace/reuse")
-					target.Containers.Put(iKey, iContainer.Clone())
+					target.Containers.Put(iKey, iContainer.Freeze())
 					bitmapIters[i].handled = true
 					continue
 				}
@@ -734,17 +797,19 @@ func (b *Bitmap) unionInPlace(others ...*Bitmap) {
 				// first other container, but for some cases, that will
 				// result in cloning a non-bitmap, then converting it
 				// to a bitmap, and this will be expensive...
-				if expectedN >= 512 && iContainer.typ != containerBitmap {
+				if expectedN >= 512 && iContainer.typ() != containerBitmap {
 					// copying the non-bitmap, then converting it,
 					// is expensive.
 					statsHit("unionInPlace/newBitmap")
-					tContainer = NewContainerBitmap(0, nil)
+					tContainer = NewContainerBitmapN(nil, 0)
 					itersToUnion = bitmapIters[i:]
 				} else {
 					// either N will be small or iContainer is a
 					// bitmap, so we can skip one union op by copying it.
+					// And we can just freeze it, and the copy will
+					// happen later if it's needed...
 					statsHit("unionInPlace/clone")
-					tContainer = iContainer.Clone()
+					tContainer = iContainer.Freeze()
 					itersToUnion = bitmapIters[i+1:]
 				}
 			} else {
@@ -753,13 +818,13 @@ func (b *Bitmap) unionInPlace(others ...*Bitmap) {
 				// convert it preemptively, because union into a
 				// bitmap is nearly always faster.
 				itersToUnion = bitmapIters[i:]
-				if expectedN >= 512 && tContainer.typ != containerBitmap {
+				if expectedN >= 512 && tContainer.typ() != containerBitmap {
 					statsHit("unionInPlace/convertToBitmap")
-					switch tContainer.typ {
+					switch tContainer.typ() {
 					case containerArray:
-						tContainer.arrayToBitmap()
+						tContainer = tContainer.arrayToBitmap()
 					case containerRun:
-						tContainer.runToBitmap()
+						tContainer = tContainer.runToBitmap()
 					}
 				}
 			}
@@ -770,6 +835,7 @@ func (b *Bitmap) unionInPlace(others ...*Bitmap) {
 				jKey, jContainer := iter.iter.Value()
 
 				if iKey == jKey {
+					tContainer = tContainer.Thaw()
 					tContainer.unionInPlace(jContainer)
 					// "iter" is a local copy from the range
 					// loop, not the actual slice member.
@@ -806,7 +872,7 @@ func (b *Bitmap) Difference(other *Bitmap) *Bitmap {
 	kj, cj := jiter.Value()
 	for i || j {
 		if i && (!j || ki < kj) {
-			output.Containers.Put(ki, ci.Clone())
+			output.Containers.Put(ki, ci.Freeze())
 			i = iiter.Next()
 			ki, ci = iiter.Value()
 		} else if j && (!i || ki > kj) {
@@ -833,11 +899,11 @@ func (b *Bitmap) Xor(other *Bitmap) *Bitmap {
 	kj, cj := jiter.Value()
 	for i || j {
 		if i && (!j || ki < kj) {
-			output.Containers.Put(ki, ci.Clone())
+			output.Containers.Put(ki, ci.Freeze())
 			i = iiter.Next()
 			ki, ci = iiter.Value()
 		} else if j && (!i || ki > kj) {
-			output.Containers.Put(kj, cj.Clone())
+			output.Containers.Put(kj, cj.Freeze())
 			j = jiter.Next()
 			kj, cj = jiter.Value()
 		} else { // ki == kj
@@ -865,7 +931,7 @@ func (b *Bitmap) Shift(n int) (*Bitmap, error) {
 		if lastCarry {
 			o.add(0)
 		}
-		if o.n > 0 {
+		if o.N() > 0 {
 			output.Containers.Put(ki, o)
 		}
 		lastCarry = carry
@@ -886,7 +952,7 @@ func (b *Bitmap) removeEmptyContainers() {
 	citer, _ := b.Containers.Iterator(0)
 	for citer.Next() {
 		k, c := citer.Value()
-		if c.n == 0 {
+		if c.N() == 0 {
 			b.Containers.Remove(k)
 		}
 	}
@@ -896,7 +962,7 @@ func (b *Bitmap) countEmptyContainers() int {
 	citer, _ := b.Containers.Iterator(0)
 	for citer.Next() {
 		_, c := citer.Value()
-		if c.n == 0 {
+		if c.N() == 0 {
 			result++
 		}
 	}
@@ -987,10 +1053,10 @@ func (b *Bitmap) writeToUnoptimized(w io.Writer) (n int64, err error) {
 		// TODO: instead of commenting this out, we need to make it a configuration option
 		//count := c.count()
 		//assert(c.count() == c.n, "cannot write container count, mismatch: count=%d, n=%d", count, c.n)
-		if c.n > 0 {
+		if c.N() > 0 {
 			ew.WriteUint64(byte8, key)
-			ew.WriteUint16(byte2, uint16(c.typ))
-			ew.WriteUint16(byte2, uint16(c.n-1))
+			ew.WriteUint16(byte2, uint16(c.typ()))
+			ew.WriteUint16(byte2, uint16(c.N()-1))
 		}
 
 	}
@@ -1001,7 +1067,7 @@ func (b *Bitmap) writeToUnoptimized(w io.Writer) (n int64, err error) {
 	citer, _ = b.Containers.Iterator(0)
 	for citer.Next() {
 		_, c := citer.Value()
-		if c.n > 0 {
+		if c.N() > 0 {
 			ew.WriteUint32(byte4, offset)
 			offset += uint32(c.size())
 		}
@@ -1017,7 +1083,7 @@ func (b *Bitmap) writeToUnoptimized(w io.Writer) (n int64, err error) {
 	citer, _ = b.Containers.Iterator(0)
 	for citer.Next() {
 		_, c := citer.Value()
-		if c.n > 0 {
+		if c.N() > 0 {
 			nn, err := c.WriteTo(w)
 			n += nn
 			if err != nil {
@@ -1074,13 +1140,17 @@ func (b *Bitmap) unmarshalPilosaRoaring(data []byte) error {
 		// Map byte slice directly to the container data.
 		citer.Next()
 		_, c := citer.Value()
-		switch c.typ {
+		// this shouldn't happen, since we don't normally store nils.
+		if c == nil {
+			continue
+		}
+		switch c.typ() {
 		case containerRun:
 			runCount := binary.LittleEndian.Uint16(data[offset : offset+runCountHeaderSize])
 			c.setRuns((*[0xFFFFFFF]interval16)(unsafe.Pointer(&data[offset+runCountHeaderSize]))[:runCount:runCount])
 			opsOffset = int(offset) + runCountHeaderSize + len(c.runs())*interval16Size
 		case containerArray:
-			c.setArray((*[0xFFFFFFF]uint16)(unsafe.Pointer(&data[offset]))[:c.n:c.n])
+			c.setArray((*[0xFFFFFFF]uint16)(unsafe.Pointer(&data[offset]))[:c.N():c.N()])
 			opsOffset = int(offset) + len(c.array())*2 // sizeof(uint32)
 		case containerBitmap:
 			c.setBitmap((*[0xFFFFFFF]uint64)(unsafe.Pointer(&data[offset]))[:bitmapN:bitmapN])
@@ -1228,6 +1298,11 @@ func (itr *Iterator) Seek(seek uint64) {
 		return // eof
 	}
 	itr.key, itr.c = itr.citer.Value()
+	if roaringParanoia {
+		if itr.c == nil {
+			panic("seeking iterator got a nil container when Next() was true")
+		}
+	}
 
 	// Move to the correct value index inside the container.
 	lb := lowbits(seek)
@@ -1283,7 +1358,7 @@ func (itr *Iterator) Next() (v uint64, eof bool) {
 	// Iterate over containers until we find the next value or EOF.
 	for {
 		if itr.c.isArray() {
-			if itr.j >= itr.c.n-1 {
+			if itr.j >= itr.c.N()-1 {
 				// Reached end of array, move to the next container.
 				if !itr.citer.Next() {
 					itr.c = nil
@@ -1419,6 +1494,9 @@ func (c *Container) count() (n int32) {
 
 // countRange counts the number of bits set between [start, end).
 func (c *Container) countRange(start, end int32) (n int32) {
+	if c == nil {
+		return 0
+	}
 	if c.isArray() {
 		return c.arrayCountRange(start, end)
 	} else if c.isRun() {
@@ -1503,73 +1581,78 @@ func (c *Container) runCountRange(start, end int32) (n int32) {
 }
 
 // add adds a value to the container.
-func (c *Container) add(v uint16) (added bool) {
-
+func (c *Container) add(v uint16) (newC *Container, added bool) {
+	if c == nil {
+		return NewContainerArray([]uint16{v}), true
+	}
 	if c.isArray() {
-		added = c.arrayAdd(v)
+		return c.arrayAdd(v)
 	} else if c.isRun() {
-		added = c.runAdd(v)
+		return c.runAdd(v)
 	} else {
-		added = c.bitmapAdd(v)
-	}
-	if added {
-		c.n++
+		return c.bitmapAdd(v)
 	}
-	return added
 }
 
-func (c *Container) arrayAdd(v uint16) bool {
+func (c *Container) arrayAdd(v uint16) (*Container, bool) {
 	// Optimize appending to the end of an array container.
 	array := c.array()
-	if c.n > 0 && c.n < ArrayMaxSize && c.isArray() && array[c.n-1] < v {
+	if c.N() > 0 && c.N() < ArrayMaxSize && c.isArray() && array[c.N()-1] < v {
 		statsHit("arrayAdd/append")
-		c.unmapArray()
+		c = c.Thaw()
 		array = append(c.array(), v)
 		c.setArray(array)
-		return true
+		return c, true
 	}
 
 	// Find index of the integer in the container. Exit if it already exists.
 	i := search32(array, v)
 	if i >= 0 {
-		return false
+		return c, false
 	}
 
 	// Convert to a bitmap container if too many values are in an array container.
-	if c.n >= ArrayMaxSize {
+	if c.N() >= ArrayMaxSize {
 		statsHit("arrayAdd/arrayToBitmap")
-		c.arrayToBitmap()
+		c = c.arrayToBitmap()
 		return c.bitmapAdd(v)
 	}
 
 	// Otherwise insert into array.
 	statsHit("arrayAdd/insert")
-	c.unmapArray()
+	c = c.Thaw()
 	i = -i - 1
 	array = append(c.array(), 0)
 	copy(array[i+1:], array[i:])
 	array[i] = v
 	c.setArray(array)
-	return true
+	return c, true
 
 }
 
-func (c *Container) bitmapAdd(v uint16) bool {
+func (c *Container) bitmapAdd(v uint16) (*Container, bool) {
+	if c == nil {
+		c = NewContainerBitmapN(nil, 1)
+		c.bitmap()[v/64] |= (1 << uint64(v%64))
+		return c, true
+	}
 	if c.bitmapContains(v) {
-		return false
+		return c, false
 	}
-	c.unmapBitmap()
+	c = c.Thaw()
 	c.bitmap()[v/64] |= (1 << uint64(v%64))
-	return true
+	c.setN(c.N() + 1)
+	return c, true
 }
 
-func (c *Container) runAdd(v uint16) bool {
+func (c *Container) runAdd(v uint16) (*Container, bool) {
 	runs := c.runs()
 
 	if len(runs) == 0 {
-		c.unmapRun()
+		c = c.Thaw()
 		c.setRuns([]interval16{{start: v, last: v}})
-		return true
+		c.setN(1)
+		return c, true
 	}
 
 	i := sort.Search(len(runs),
@@ -1581,10 +1664,10 @@ func (c *Container) runAdd(v uint16) bool {
 
 	iv := runs[i]
 	if v >= iv.start && iv.last >= v {
-		return false
+		return c, false
 	}
 
-	c.unmapRun()
+	c = c.Thaw()
 	runs = c.runs()
 	if iv.last < v {
 		if iv.last == v-1 {
@@ -1598,7 +1681,8 @@ func (c *Container) runAdd(v uint16) bool {
 			runs[i-1].last = iv.last
 			runs = append(runs[:i], runs[i+1:]...)
 			c.setRuns(runs)
-			return true
+			c.setN(c.N() + 1)
+			return c, true
 		}
 		// just before an interval
 		runs[i].start--
@@ -1611,11 +1695,15 @@ func (c *Container) runAdd(v uint16) bool {
 		runs = append(runs[:i], append([]interval16{newIv}, runs[i:]...)...)
 	}
 	c.setRuns(runs)
-	return true
+	c.setN(c.N() + 1)
+	return c, true
 }
 
 // Contains returns true if v is in the container.
 func (c *Container) Contains(v uint16) bool {
+	if c == nil {
+		return false
+	}
 	if c.isArray() {
 		return c.arrayContains(v)
 	} else if c.isRun() {
@@ -1669,17 +1757,17 @@ func (c *Container) countRuns() (r int32) {
 
 // optimize converts the container to the type which will take up the least
 // amount of space.
-func (c *Container) optimize() {
-	if c.n == 0 {
+func (c *Container) optimize() *Container {
+	if c.N() == 0 {
 		statsHit("optimize/empty")
-		return
+		return nil
 	}
 	runs := c.countRuns()
 
 	var newType byte
-	if runs <= runMaxSize && runs <= c.n/2 {
+	if runs <= runMaxSize && runs <= c.N()/2 {
 		newType = containerRun
-	} else if c.n < ArrayMaxSize {
+	} else if c.N() < ArrayMaxSize {
 		newType = containerArray
 	} else {
 		newType = containerBitmap
@@ -1689,75 +1777,94 @@ func (c *Container) optimize() {
 	if c.isArray() {
 		if newType == containerBitmap {
 			statsHit("optimize/arrayToBitmap")
-			c.arrayToBitmap()
+			c = c.arrayToBitmap()
 		} else if newType == containerRun {
 			statsHit("optimize/arrayToRun")
-			c.arrayToRun(runs)
+			c = c.arrayToRun(runs)
 		} else {
 			statsHit("optimize/arrayUnchanged")
 		}
 	} else if c.isBitmap() {
 		if newType == containerArray {
 			statsHit("optimize/bitmapToArray")
-			c.bitmapToArray()
+			c = c.bitmapToArray()
 		} else if newType == containerRun {
 			statsHit("optimize/bitmapToRun")
-			c.bitmapToRun(runs)
+			c = c.bitmapToRun(runs)
 		} else {
 			statsHit("optimize/bitmapUnchanged")
 		}
 	} else if c.isRun() {
 		if newType == containerBitmap {
 			statsHit("optimize/runToBitmap")
-			c.runToBitmap()
+			c = c.runToBitmap()
 		} else if newType == containerArray {
 			statsHit("optimize/runToArray")
-			c.runToArray()
+			c = c.runToArray()
 		} else {
 			statsHit("optimize/runUnchanged")
 		}
 	}
+	return c
 }
 
 // unionInPlace does not necessarily preserve container's N; it's expected
 // to be used when running a sequence of unions, after which you should
 // call Repair(). (As of this writing, that only matters for bitmaps.)
-func (c *Container) unionInPlace(other *Container) {
-	switch c.typ {
+//
+// If called on a frozen container, or a container of the wrong sort,
+// it is possible that the returned container will not actually be the
+// original container; in-place is a suggestion.
+func (c *Container) unionInPlace(other *Container) *Container {
+	if c == nil {
+		return other.Freeze()
+	}
+	if other == nil {
+		return c
+	}
+	// short-circuit the trivial cases
+	if c.N() == maxContainerVal+1 || other.N() == maxContainerVal+1 {
+		return fullContainer
+	}
+	switch c.typ() {
 	case containerBitmap:
-		switch other.typ {
+		switch other.typ() {
 		case containerBitmap:
-			unionBitmapBitmapInPlace(c, other)
+			return unionBitmapBitmapInPlace(c, other)
 		case containerArray:
-			unionBitmapArrayInPlace(c, other)
+			return unionBitmapArrayInPlace(c, other)
 		case containerRun:
-			unionBitmapRunInPlace(c, other)
+			return unionBitmapRunInPlace(c, other)
 
 		}
 	case containerArray:
-		switch other.typ {
+		switch other.typ() {
 		case containerBitmap:
-			c.arrayToBitmap()
-			unionBitmapBitmapInPlace(c, other)
+			c = c.arrayToBitmap()
+			return unionBitmapBitmapInPlace(c, other)
 		case containerArray:
-			unionArrayArrayInPlace(c, other)
+			return unionArrayArrayInPlace(c, other)
 		case containerRun:
-			c.arrayToBitmap()
-			unionBitmapRunInPlace(c, other)
+			c = c.arrayToBitmap()
+			return unionBitmapRunInPlace(c, other)
 		}
 	case containerRun:
-		switch other.typ {
+		switch other.typ() {
 		case containerBitmap:
-			c.runToBitmap()
-			unionBitmapBitmapInPlace(c, other)
+			c = c.runToBitmap()
+			return unionBitmapBitmapInPlace(c, other)
 		case containerArray:
-			c.runToBitmap()
-			unionBitmapArrayInPlace(c, other)
+			c = c.runToBitmap()
+			return unionBitmapArrayInPlace(c, other)
 		case containerRun:
-			c.runToBitmap()
-			unionBitmapRunInPlace(c, other)
+			c = c.runToBitmap()
+			return unionBitmapRunInPlace(c, other)
 		}
 	}
+	if roaringParanoia {
+		panic(fmt.Sprintf("invalid union op: unknown types %d/%d", c.typ(), other.typ()))
+	}
+	return c
 }
 
 func (c *Container) arrayContains(v uint16) bool {
@@ -1788,58 +1895,71 @@ func (c *Container) runContains(v uint16) bool {
 }
 
 // remove removes a value from the container.
-func (c *Container) remove(v uint16) (removed bool) {
+func (c *Container) remove(v uint16) (newC *Container, removed bool) {
+	if c == nil {
+		return nil, false
+	}
 	if c.isArray() {
-		removed = c.arrayRemove(v)
+		return c.arrayRemove(v)
 	} else if c.isRun() {
-		removed = c.runRemove(v)
+		return c.runRemove(v)
 	} else {
-		removed = c.bitmapRemove(v)
+		return c.bitmapRemove(v)
 	}
-	return removed
 }
 
-func (c *Container) arrayRemove(v uint16) bool {
+func (c *Container) arrayRemove(v uint16) (*Container, bool) {
 	array := c.array()
 	i := search32(array, v)
 	if i < 0 {
-		return false
+		return c, false
+	}
+	// removing the last item? we can just return the empty container.
+	if c.N() == 1 {
+		return nil, true
 	}
-	c.unmapArray()
+	c = c.Thaw()
 	array = c.array()
 
 	array = append(array[:i], array[i+1:]...)
-	c.n--
 	c.setArray(array)
-	return true
+	return c, true
 }
 
-func (c *Container) bitmapRemove(v uint16) bool {
+func (c *Container) bitmapRemove(v uint16) (*Container, bool) {
 	if !c.bitmapContains(v) {
-		return false
+		return c, false
 	}
-	c.unmapBitmap()
+	// removing the last item? we can just return the empty container.
+	if c.N() == 1 {
+		return nil, true
+	}
+	c = c.Thaw()
 
 	// Lower count and remove element.
 	c.bitmap()[v/64] &^= (uint64(1) << uint(v%64))
-	c.n--
+	c.setN(c.N() - 1)
 
 	// Convert to array if we go below the threshold.
-	if c.n == ArrayMaxSize {
+	if c.N() == ArrayMaxSize {
 		statsHit("bitmapRemove/bitmapToArray")
-		c.bitmapToArray()
+		c = c.bitmapToArray()
 	}
-	return true
+	return c, true
 }
 
 // runRemove removes v from a run container, and returns true if v was removed.
-func (c *Container) runRemove(v uint16) bool {
+func (c *Container) runRemove(v uint16) (*Container, bool) {
 	runs := c.runs()
 	i, contains := binSearchRuns(v, runs)
 	if !contains {
-		return false
+		return c, false
+	}
+	// removing the last item? we can just return the empty container.
+	if c.N() == 1 {
+		return nil, true
 	}
-	c.unmapRun()
+	c = c.Thaw()
 	runs = c.runs()
 	if v == runs[i].last && v == runs[i].start {
 		runs = append(runs[:i], runs[i+1:]...)
@@ -1855,13 +1975,17 @@ func (c *Container) runRemove(v uint16) bool {
 		runs[i+1] = interval16{start: v + 1, last: last}
 		// runs = append(runs[:i+1], append([]interval16{{start: v + 1, last: last}}, runs[i+1:]...)...)
 	}
-	c.n--
+	c.setN(c.N() - 1)
 	c.setRuns(runs)
-	return true
+	return c, true
 }
 
 // max returns the maximum value in the container.
 func (c *Container) max() uint16 {
+	if c == nil || c.N() == 0 {
+		// probably wrong, but prevents a crash elsewhere
+		return 0
+	}
 	if c.isArray() {
 		return c.arrayMax()
 	} else if c.isRun() {
@@ -1873,9 +1997,6 @@ func (c *Container) max() uint16 {
 
 func (c *Container) arrayMax() uint16 {
 	array := c.array()
-	if len(array) == 0 {
-		return 0 // probably hiding some ugly bug but it prevents a crash
-	}
 	return array[len(array)-1]
 }
 
@@ -1903,26 +2024,33 @@ func (c *Container) runMax() uint16 {
 }
 
 // bitmapToArray converts from bitmap format to array format.
-func (c *Container) bitmapToArray() {
+func (c *Container) bitmapToArray() *Container {
 	statsHit("bitmapToArray")
-	bitmap := c.bitmap()
-	c.setBitmap(nil)
-	c.typ = containerArray
-	c.mapped = false
-
-	// return early if empty
-	if c.n == 0 {
+	if c == nil {
+		if roaringParanoia {
+			panic("nil container for bitmapToArray")
+		}
+		return nil
+	}
+	// If c is frozen, we'll be making a new array container. Otherwise,
+	// we'll convert this container.
+	if c.N() == 0 {
+		if c.frozen() {
+			return NewContainerArray(nil)
+		}
+		c.setTyp(containerArray)
 		c.setArray(nil)
-		return
+		return c
 	}
+	bitmap := c.bitmap()
 	n := int32(0)
 
-	array := make([]uint16, c.n)
+	array := make([]uint16, c.N())
 	for i, word := range bitmap {
 		for word != 0 {
 			t := word & -word
 			if roaringParanoia {
-				if n >= c.n {
+				if n >= c.N() {
 					panic("bitmap has more bits set than container.n")
 				}
 			}
@@ -1932,71 +2060,112 @@ func (c *Container) bitmapToArray() {
 		}
 	}
 	if roaringParanoia {
-		if n != c.n {
+		if n != c.N() {
 			panic("bitmap has fewer bits set than container.n")
 		}
 	}
+	if c.frozen() {
+		return NewContainerArray(array)
+	}
+	c.setTyp(containerArray)
+	c.setMapped(false)
 	c.setArray(array)
+	return c
 }
 
 // arrayToBitmap converts from array format to bitmap format.
-func (c *Container) arrayToBitmap() {
+func (c *Container) arrayToBitmap() *Container {
 	statsHit("arrayToBitmap")
-	array := c.array()
-	c.typ = containerBitmap
-	bitmap := make([]uint64, bitmapN)
-	c.setBitmap(bitmap)
-	c.mapped = false
+	if c == nil {
+		if roaringParanoia {
+			panic("nil container for arrayToBitmap")
+		}
+		return nil
+	}
 
 	// return early if empty
-	if c.n == 0 {
-		return
+	if c.N() == 0 {
+		if c.frozen() {
+			return NewContainerBitmap(0, nil)
+		}
+		c.setTyp(containerBitmap)
+		c.setBitmap(make([]uint64, bitmapN))
+		return c
 	}
 
-	for _, v := range array {
+	bitmap := make([]uint64, bitmapN)
+	for _, v := range c.array() {
 		bitmap[int(v)/64] |= (uint64(1) << uint(v%64))
 	}
+	if c.frozen() {
+		return NewContainerBitmapN(bitmap, c.N())
+	}
+	c.setTyp(containerBitmap)
+	c.setMapped(false)
+	c.setBitmap(bitmap)
+	return c
 }
 
 // runToBitmap converts from RLE format to bitmap format.
-func (c *Container) runToBitmap() {
+func (c *Container) runToBitmap() *Container {
 	statsHit("runToBitmap")
-	runs := c.runs()
-	bitmap := make([]uint64, bitmapN)
-	c.typ = containerBitmap
-	c.setBitmap(bitmap)
-
-	c.mapped = false
+	if c == nil {
+		if roaringParanoia {
+			panic("nil container for runToBitmap")
+		}
+		return nil
+	}
 
 	// return early if empty
-	if c.n == 0 {
-		return
+	if c.N() == 0 {
+		if c.frozen() {
+			return NewContainerBitmap(0, nil)
+		}
+		c.setTyp(containerBitmap)
+		c.setBitmap(make([]uint64, bitmapN))
+		return c
 	}
-
-	for _, r := range runs {
+	bitmap := make([]uint64, bitmapN)
+	for _, r := range c.runs() {
 		// TODO this can be ~64x faster for long runs by setting maxBitmap instead of single bits
 		//note v must be int or will overflow
 		for v := int(r.start); v <= int(r.last); v++ {
 			bitmap[v/64] |= (uint64(1) << uint(v%64))
 		}
 	}
+	if c.frozen() {
+		return NewContainerBitmapN(bitmap, c.N())
+	}
+	c.setTyp(containerBitmap)
+	c.setMapped(false)
+	c.setBitmap(bitmap)
+	return c
 }
 
 // bitmapToRun converts from bitmap format to RLE format.
-func (c *Container) bitmapToRun(numRuns int32) {
+func (c *Container) bitmapToRun(numRuns int32) *Container {
 	statsHit("bitmapToRun")
-	bitmap := c.bitmap()
-	c.mapped = false
-	c.typ = containerRun
+	if c == nil {
+		if roaringParanoia {
+			panic("nil container for bitmapToRun")
+		}
+		return nil
+	}
+
 	// return early if empty
-	if c.n == 0 {
+	if c.N() == 0 {
+		if c.frozen() {
+			return NewContainerRun(nil)
+		}
+		c.setTyp(containerRun)
 		c.setRuns(nil)
-		return
+		return c
 	}
+
+	bitmap := c.bitmap()
 	if numRuns == 0 {
 		numRuns = bitmapCountRuns(bitmap)
 	}
-
 	runs := make([]interval16, 0, numRuns)
 
 	current := bitmap[0]
@@ -2036,20 +2205,37 @@ func (c *Container) bitmapToRun(numRuns int32) {
 		// pad LSBs with 0s
 		current = current & (current + 1)
 	}
+	if c.frozen() {
+		return NewContainerRunN(runs, c.N())
+	}
+	c.setTyp(containerRun)
 	c.setRuns(runs)
+	c.setMapped(false)
+	return c
 }
 
 // arrayToRun converts from array format to RLE format.
-func (c *Container) arrayToRun(numRuns int32) {
+func (c *Container) arrayToRun(numRuns int32) *Container {
 	statsHit("arrayToRun")
-	array := c.array()
-	c.typ = containerRun
-	c.mapped = false
+	if c == nil {
+		if roaringParanoia {
+			panic("nil container for arrayToRun")
+		}
+		return nil
+	}
+
 	// return early if empty
-	if c.n == 0 {
+	if c.N() == 0 {
+		if c.frozen() {
+			return NewContainerRun(nil)
+		}
+		c.setTyp(containerRun)
 		c.setRuns(nil)
-		return
+		return c
 	}
+
+	array := c.array()
+
 	if numRuns == 0 {
 		numRuns = arrayCountRuns(array)
 	}
@@ -2064,24 +2250,39 @@ func (c *Container) arrayToRun(numRuns int32) {
 		}
 	}
 	// append final run
-	runs = append(runs, interval16{start, array[c.n-1]})
+	runs = append(runs, interval16{start, array[c.N()-1]})
+	if c.frozen() {
+		return NewContainerRunN(runs, c.N())
+	}
+	c.setTyp(containerRun)
+	c.setMapped(false)
 	c.setRuns(runs)
+	return c
 }
 
 // runToArray converts from RLE format to array format.
-func (c *Container) runToArray() {
+func (c *Container) runToArray() *Container {
 	statsHit("runToArray")
-	runs := c.runs()
-	c.typ = containerArray
-	c.mapped = false
+	if c == nil {
+		if roaringParanoia {
+			panic("nil container for runToArray")
+		}
+		return nil
+	}
 
 	// return early if empty
-	if c.n == 0 {
+	if c.N() == 0 {
+		if c.frozen() {
+			return NewContainerArray(nil)
+		}
+		c.setTyp(containerArray)
 		c.setArray(nil)
-		return
+		return c
 	}
 
-	array := make([]uint16, c.n)
+	runs := c.runs()
+
+	array := make([]uint16, c.N())
 	n := int32(0)
 	for _, r := range runs {
 		for v := int(r.start); v <= int(r.last); v++ {
@@ -2090,38 +2291,43 @@ func (c *Container) runToArray() {
 		}
 	}
 	if roaringParanoia {
-		if n != c.n {
+		if n != c.N() {
 			panic("run has fewer bits set than container.n")
 		}
 	}
+	if c.frozen() {
+		return NewContainerArray(array)
+	}
+	c.setTyp(containerArray)
+	c.setMapped(false)
 	c.setArray(array)
+	return c
 }
 
 // Clone returns a copy of c.
 func (c *Container) Clone() (out *Container) {
 	statsHit("Container/Clone")
-	switch c.typ {
+	if c == nil {
+		return nil
+	}
+	switch c.typ() {
 	case containerArray:
 		statsHit("Container/Clone/Array")
-		cArray := c.array()
-		array := make([]uint16, len(cArray))
-		copy(array, cArray)
-		out = NewContainerArray(array)
+		out = NewContainerArrayCopy(c.array())
 	case containerBitmap:
 		statsHit("Container/Clone/Bitmap")
-		other := NewContainerBitmap(c.n, nil)
+		other := NewContainerBitmapN(nil, c.N())
 		copy(other.bitmap(), c.bitmap())
 		out = other
 	case containerRun:
 		statsHit("Container/Clone/Run")
-		cRuns := c.runs()
-		runs := make([]interval16, len(cRuns))
-		copy(runs, cRuns)
-		out = NewContainerRun(runs)
+		out = NewContainerRunCopy(c.runs())
+	default:
+		panic(fmt.Sprintf("cloning a container of unknown type %d", c.typ()))
 	}
 	// this should probably never happen
 	if roaringParanoia {
-		if out.n != out.count() {
+		if out.N() != out.count() {
 			panic("cloned container has wrong n")
 		}
 	}
@@ -2130,6 +2336,9 @@ func (c *Container) Clone() (out *Container) {
 
 // WriteTo writes c to w.
 func (c *Container) WriteTo(w io.Writer) (n int64, err error) {
+	if c == nil {
+		return 0, nil
+	}
 	if c.isArray() {
 		return c.arrayWriteTo(w)
 	} else if c.isRun() {
@@ -2153,7 +2362,7 @@ func (c *Container) arrayWriteTo(w io.Writer) (n int64, err error) {
 	//}
 
 	// Write sizeof(uint16) * cardinality bytes.
-	nn, err := w.Write((*[0xFFFFFFF]byte)(unsafe.Pointer(&array[0]))[: 2*c.n : 2*c.n])
+	nn, err := w.Write((*[0xFFFFFFF]byte)(unsafe.Pointer(&array[0]))[: 2*c.N() : 2*c.N()])
 	return int64(nn), err
 }
 
@@ -2194,7 +2403,12 @@ func (c *Container) size() int {
 
 // info returns the current stats about the container.
 func (c *Container) info() containerInfo {
-	info := containerInfo{N: c.n}
+	info := containerInfo{N: c.N()}
+	if c == nil {
+		info.Type = "nil"
+		info.Alloc = 0
+		return info
+	}
 
 	if c.isArray() {
 		info.Type = "array"
@@ -2207,7 +2421,7 @@ func (c *Container) info() containerInfo {
 		info.Alloc = len(c.bitmap()) * 8 // sizeof(uint64)
 	}
 
-	if c.mapped {
+	if c.Mapped() {
 		if c.isArray() {
 			info.Pointer = unsafe.Pointer(&c.array()[0])
 		} else if c.isRun() {
@@ -2224,24 +2438,27 @@ func (c *Container) info() containerInfo {
 func (c *Container) check() error {
 	var a ErrorList
 
+	if c == nil {
+		return nil
+	}
 	if c.isArray() {
 		array := c.array()
-		if int32(len(array)) != c.n {
-			a.Append(fmt.Errorf("array count mismatch: count=%d, n=%d", len(array), c.n))
+		if int32(len(array)) != c.N() {
+			a.Append(fmt.Errorf("array count mismatch: count=%d, n=%d", len(array), c.N()))
 		}
 	} else if c.isRun() {
 		n := c.runCountRange(0, maxContainerVal+1)
-		if n != c.n {
-			a.Append(fmt.Errorf("run count mismatch: count=%d, n=%d", n, c.n))
+		if n != c.N() {
+			a.Append(fmt.Errorf("run count mismatch: count=%d, n=%d", n, c.N()))
 		}
 	} else if c.isBitmap() {
-		if n := c.bitmapCountRange(0, maxContainerVal+1); n != c.n {
-			a.Append(fmt.Errorf("bitmap count mismatch: count=%d, n=%d", n, c.n))
+		if n := c.bitmapCountRange(0, maxContainerVal+1); n != c.N() {
+			a.Append(fmt.Errorf("bitmap count mismatch: count=%d, n=%d", n, c.N()))
 		}
 	} else {
 		a.Append(fmt.Errorf("empty container"))
-		if c.n != 0 {
-			a.Append(fmt.Errorf("empty container with nonzero count: n=%d", c.n))
+		if c.N() != 0 {
+			a.Append(fmt.Errorf("empty container with nonzero count: n=%d", c.N()))
 		}
 	}
 
@@ -2254,6 +2471,11 @@ func (c *Container) check() error {
 // Repair repairs the cardinality of c if it has been corrupted by
 // optimized operations.
 func (c *Container) Repair() {
+	// a frozen container can't have had n or contents changed, so we
+	// don't need to recount it.
+	if c.frozen() {
+		return
+	}
 	if c.isBitmap() {
 		c.bitmapRepair()
 	}
@@ -2271,7 +2493,7 @@ func (c *Container) bitmapRepair() {
 		n += int32(popcount(bitmap[i+2]))
 		n += int32(popcount(bitmap[i+3]))
 	}
-	c.n = n
+	c.setN(n)
 }
 
 // containerInfo represents a point-in-time snapshot of container stats.
@@ -2299,20 +2521,20 @@ func flipArray(b *Container) *Container {
 	statsHit("flipArray")
 	// TODO: actually implement this
 	x := b.Clone()
-	x.arrayToBitmap()
+	x = x.arrayToBitmap()
 	return flipBitmap(x)
 }
 
 func flipBitmap(b *Container) *Container {
 	statsHit("flipBitmap")
-	other := NewContainerBitmap(0, nil)
+	other := NewContainerBitmapN(nil, 0)
 	bitmap := b.bitmap()
 	otherBitmap := other.bitmap()
 	for i, word := range bitmap {
 		otherBitmap[i] = ^word
 	}
 
-	other.n = other.count()
+	other.setN(other.count())
 	return other
 }
 
@@ -2320,11 +2542,20 @@ func flipRun(b *Container) *Container {
 	statsHit("flipRun")
 	// TODO: actually implement this
 	x := b.Clone()
-	x.runToBitmap()
+	x = x.runToBitmap()
 	return flipBitmap(x)
 }
 
 func intersectionCount(a, b *Container) int32 {
+	if a.N() == maxContainerVal+1 {
+		return b.N()
+	}
+	if b.N() == maxContainerVal+1 {
+		return a.N()
+	}
+	if a.N() == 0 || b.N() == 0 {
+		return 0
+	}
 	if a.isArray() {
 		if b.isArray() {
 			return intersectionCountArrayArray(a, b)
@@ -2356,9 +2587,6 @@ func intersectionCountArrayArray(a, b *Container) (n int32) {
 	statsHit("intersectionCount/ArrayArray")
 	ca, cb := a.array(), b.array()
 	na, nb := len(ca), len(cb)
-	if na == 0 || nb == 0 {
-		return 0
-	}
 	if na > nb {
 		ca, cb = cb, ca
 		na, nb = nb, na // nolint: ineffassign
@@ -2458,6 +2686,15 @@ func intersectionCountBitmapBitmap(a, b *Container) (n int32) {
 }
 
 func intersect(a, b *Container) *Container {
+	if a.N() == maxContainerVal+1 {
+		return b.Freeze()
+	}
+	if b.N() == maxContainerVal+1 {
+		return a.Freeze()
+	}
+	if a.N() == 0 || b.N() == 0 {
+		return nil
+	}
 	if a.isArray() {
 		if b.isArray() {
 			return intersectArrayArray(a, b)
@@ -2532,6 +2769,7 @@ func intersectRunRun(a, b *Container) *Container {
 	output := NewContainerRun(nil)
 	ra, rb := a.runs(), b.runs()
 	na, nb := len(ra), len(rb)
+	n := int32(0)
 	for i, j := 0, 0; i < na && j < nb; {
 		va, vb := ra[i], rb[j]
 		if va.last < vb.start {
@@ -2542,24 +2780,25 @@ func intersectRunRun(a, b *Container) *Container {
 			j++
 		} else if va.last > vb.last && va.start >= vb.start {
 			// |--vb-|-|-va--|
-			output.n += output.runAppendInterval(interval16{start: va.start, last: vb.last})
+			n += output.runAppendInterval(interval16{start: va.start, last: vb.last})
 			j++
 		} else if va.last > vb.last && va.start < vb.start {
 			// |--va|--vb--|--|
-			output.n += output.runAppendInterval(vb)
+			n += output.runAppendInterval(vb)
 			j++
 		} else if va.last <= vb.last && va.start >= vb.start {
 			// |--vb|--va--|--|
-			output.n += output.runAppendInterval(va)
+			n += output.runAppendInterval(va)
 			i++
 		} else if va.last <= vb.last && va.start < vb.start {
 			// |--va-|-|-vb--|
-			output.n += output.runAppendInterval(interval16{start: vb.start, last: va.last})
+			n += output.runAppendInterval(interval16{start: vb.start, last: va.last})
 			i++
 		}
 	}
+	output.setN(n)
 	runs := output.runs()
-	if output.n < ArrayMaxSize && int32(len(runs)) > output.n/2 {
+	if n < ArrayMaxSize && int32(len(runs)) > n/2 {
 		output.runToArray()
 	} else if len(runs) > runMaxSize {
 		output.runToBitmap()
@@ -2573,9 +2812,9 @@ func intersectBitmapRun(a, b *Container) *Container {
 	statsHit("intersect/BitmapRun")
 	var output *Container
 	runs := b.runs()
-	if b.n <= ArrayMaxSize || a.n <= ArrayMaxSize {
+	if b.N() <= ArrayMaxSize || a.N() <= ArrayMaxSize {
 		// output is array container
-		array := make([]uint16, 0, b.n)
+		array := make([]uint16, 0, b.N())
 		for _, iv := range runs {
 			for i := iv.start; i <= iv.last; i++ {
 				if a.bitmapContains(i) {
@@ -2596,6 +2835,7 @@ func intersectBitmapRun(a, b *Container) *Container {
 		output = NewContainerBitmap(0, nil)
 		bitmap := output.bitmap()
 		aBitmap := a.bitmap()
+		n := int32(0)
 		for j := 0; j < len(runs); j++ {
 			vb := runs[j]
 			i := vb.start >> 6 // index into a
@@ -2604,22 +2844,22 @@ func intersectBitmapRun(a, b *Container) *Container {
 			for valast >= vb.start && vastart <= vb.last && i < bitmapN {
 				if vastart >= vb.start && valast <= vb.last { // a within b
 					bitmap[i] = aBitmap[i]
-					output.n += int32(popcount(aBitmap[i]))
+					n += int32(popcount(aBitmap[i]))
 				} else if vb.start >= vastart && vb.last <= valast { // b within a
 					var mask uint64 = ((1 << (vb.last - vb.start + 1)) - 1) << (vb.start - vastart)
 					bits := aBitmap[i] & mask
 					bitmap[i] |= bits
-					output.n += int32(popcount(bits))
+					n += int32(popcount(bits))
 				} else if vastart < vb.start { // a overlaps front of b
 					offset := 64 - (1 + valast - vb.start)
 					bits := (aBitmap[i] >> offset) << offset
 					bitmap[i] |= bits
-					output.n += int32(popcount(bits))
+					n += int32(popcount(bits))
 				} else if vb.start < vastart { // b overlaps front of a
 					offset := 64 - (1 + vb.last - vastart)
 					bits := (aBitmap[i] << offset) >> offset
 					bitmap[i] |= bits
-					output.n += int32(popcount(bits))
+					n += int32(popcount(bits))
 				}
 				// update loop vars
 				i++
@@ -2627,6 +2867,7 @@ func intersectBitmapRun(a, b *Container) *Container {
 				valast = vastart + 63
 			}
 		}
+		output.setN(n)
 	}
 	return output
 }
@@ -2662,11 +2903,14 @@ func intersectBitmapBitmap(a, b *Container) *Container {
 		n += int32(popcount(ob[i]))
 	}
 
-	output := NewContainerBitmap(n, ob)
+	output := NewContainerBitmapN(ob, n)
 	return output
 }
 
 func union(a, b *Container) *Container {
+	if a.N() == maxContainerVal+1 || b.N() == maxContainerVal+1 {
+		return fullContainer
+	}
 	if a.isArray() {
 		if b.isArray() {
 			return unionArrayArray(a, b)
@@ -2736,7 +2980,7 @@ func unionArrayArray(a, b *Container) *Container {
 // unionArrayArrayInPlace does what it sounds like -- tries to combine
 // the two arrays in-place. It does not try to ensure that the result is
 // of a good array size, so it could be up to twice that size, temporarily.
-func unionArrayArrayInPlace(a, b *Container) {
+func unionArrayArrayInPlace(a, b *Container) *Container {
 	statsHit("union/ArrayArrayInPlace")
 	aa, ab := a.array(), b.array()
 	na, nb := len(aa), len(ab)
@@ -2771,25 +3015,26 @@ func unionArrayArrayInPlace(a, b *Container) {
 			j++
 		}
 	}
-	a.setArray(output[:outN])
-	a.n = int32(outN)
-	if a.n > ArrayMaxSize {
-		a.optimize()
+	// a union can't omit anything that was previously in a, so if
+	// the output is the same length, nothing changed.
+	if len(output) != int(a.N()) {
+		a = a.Thaw()
+		a.setArray(output[:outN])
+		a = a.optimize()
 	}
+	return a
 }
 
 // unionArrayRun optimistically assumes that the result will be a run container,
 // and converts to a bitmap or array container afterwards if necessary.
 func unionArrayRun(a, b *Container) *Container {
 	statsHit("union/ArrayRun")
-	if b.n == maxContainerVal+1 {
-		return b.Clone()
-	}
 	output := NewContainerRun(nil)
 	aa, rb := a.array(), b.runs()
 	na, nb := len(aa), len(rb)
 	var vb interval16
 	var va uint16
+	n := int32(0)
 	for i, j := 0, 0; i < na || j < nb; {
 		if i < na {
 			va = aa[i]
@@ -2798,17 +3043,18 @@ func unionArrayRun(a, b *Container) *Container {
 			vb = rb[j]
 		}
 		if i < na && (j >= nb || va < vb.start) {
-			output.n += output.runAppendInterval(interval16{start: va, last: va})
+			n += output.runAppendInterval(interval16{start: va, last: va})
 			i++
 		} else {
-			output.n += output.runAppendInterval(vb)
+			n += output.runAppendInterval(vb)
 			j++
 		}
 	}
-	if output.n < ArrayMaxSize {
-		output.runToArray()
+	output.setN(n)
+	if n < ArrayMaxSize {
+		output = output.runToArray()
 	} else if len(output.runs()) > runMaxSize {
-		output.runToBitmap()
+		output = output.runToBitmap()
 	}
 	return output
 }
@@ -2845,16 +3091,11 @@ func (c *Container) runAppendInterval(v interval16) int32 {
 
 func unionRunRun(a, b *Container) *Container {
 	statsHit("union/RunRun")
-	if a.n == maxContainerVal+1 {
-		return a.Clone()
-	}
-	if b.n == maxContainerVal+1 {
-		return b.Clone()
-	}
 	ra, rb := a.runs(), b.runs()
 	na, nb := len(ra), len(rb)
 	output := NewContainerRun(make([]interval16, 0, na+nb))
 	var va, vb interval16
+	n := int32(0)
 	for i, j := 0, 0; i < na || j < nb; {
 		if i < na {
 			va = ra[i]
@@ -2863,13 +3104,14 @@ func unionRunRun(a, b *Container) *Container {
 			vb = rb[j]
 		}
 		if i < na && (j >= nb || va.start < vb.start) {
-			output.n += output.runAppendInterval(va)
+			n += output.runAppendInterval(va)
 			i++
 		} else {
-			output.n += output.runAppendInterval(vb)
+			n += output.runAppendInterval(vb)
 			j++
 		}
 	}
+	output.setN(n)
 	if len(output.runs()) > runMaxSize {
 		output.runToBitmap()
 	}
@@ -2878,55 +3120,52 @@ func unionRunRun(a, b *Container) *Container {
 
 func unionBitmapRun(a, b *Container) *Container {
 	statsHit("union/BitmapRun")
-	if b.n == maxContainerVal+1 {
-		return b.Clone()
-	}
-	if a.n == maxContainerVal+1 {
-		return a.Clone()
-	}
 	output := a.Clone()
-	bitmap := output.bitmap()
 	for _, run := range b.runs() {
-		output.bitmapSetRange(bitmap, uint64(run.start), uint64(run.last)+1)
+		output.bitmapSetRange(uint64(run.start), uint64(run.last)+1)
 	}
 	return output
 }
 
 // unions the run b into the bitmap a, mutating a in place. The n value of
 // a will need to be repaired after the fact.
-func unionBitmapRunInPlace(a, b *Container) {
-	a.unmapBitmap()
+func unionBitmapRunInPlace(a, b *Container) *Container {
+	a = a.Thaw()
 	bitmap := a.bitmap()
 	statsHit("union/BitmapRun")
 	for _, run := range b.runs() {
 		bitmapSetRangeIgnoreN(bitmap, uint64(run.start), uint64(run.last)+1)
 	}
+	return a
 }
 
 const maxBitmap = 0xFFFFFFFFFFFFFFFF
 
 // sets all bits in [i, j) (c must be a bitmap container, and bitmap must
 // be its bitmap).
-func (c *Container) bitmapSetRange(bitmap []uint64, i, j uint64) {
+func (c *Container) bitmapSetRange(i, j uint64) {
+	bitmap := c.bitmap()
 	x := i >> 6
 	y := (j - 1) >> 6
 	var X uint64 = maxBitmap << (i % 64)
 	var Y uint64 = maxBitmap >> (63 - ((j - 1) % 64))
 	xcnt := popcount(X)
 	ycnt := popcount(Y)
+	n := int32(c.N())
 	if x == y {
-		c.n += int32((j - i) - popcount(bitmap[x]&(X&Y)))
+		n += int32((j - i) - popcount(bitmap[x]&(X&Y)))
 		bitmap[x] |= (X & Y)
 	} else {
-		c.n += int32(xcnt - popcount(bitmap[x]&X))
+		n += int32(xcnt - popcount(bitmap[x]&X))
 		bitmap[x] |= X
 		for i := x + 1; i < y; i++ {
-			c.n += int32(64 - popcount(bitmap[i]))
+			n += int32(64 - popcount(bitmap[i]))
 			bitmap[i] = maxBitmap
 		}
-		c.n += int32(ycnt - popcount(bitmap[y]&Y))
+		n += int32(ycnt - popcount(bitmap[y]&Y))
 		bitmap[y] |= Y
 	}
+	c.setN(n)
 }
 
 // sets all bits in [i, j) without updating any corresponding n value.
@@ -2954,23 +3193,25 @@ func (c *Container) bitmapXorRange(i, j uint64) {
 	var X uint64 = maxBitmap << (i % 64)
 	var Y uint64 = maxBitmap >> (63 - ((j - 1) % 64))
 	bitmap := c.bitmap()
+	n := c.N()
 	if x == y {
 		cnt := popcount(bitmap[x])
 		bitmap[x] ^= (X & Y) //// flip
-		c.n += int32(popcount(bitmap[x]) - cnt)
+		n += int32(popcount(bitmap[x]) - cnt)
 	} else {
 		cnt := popcount(bitmap[x])
 		bitmap[x] ^= X
-		c.n += int32(popcount(bitmap[x]) - cnt)
+		n += int32(popcount(bitmap[x]) - cnt)
 		for i := x + 1; i < y; i++ {
 			cnt = popcount(bitmap[i])
 			bitmap[i] ^= maxBitmap
-			c.n += int32(popcount(bitmap[i]) - cnt)
+			n += int32(popcount(bitmap[i]) - cnt)
 		}
 		cnt = popcount(bitmap[y])
 		bitmap[y] ^= Y
-		c.n += int32(popcount(bitmap[y]) - cnt)
+		n += int32(popcount(bitmap[y]) - cnt)
 	}
+	c.setN(n)
 }
 
 // zeroes all bits in [i, j) (c must be a bitmap container)
@@ -2980,26 +3221,34 @@ func (c *Container) bitmapZeroRange(i, j uint64) {
 	var X uint64 = maxBitmap << (i % 64)
 	var Y uint64 = maxBitmap >> (63 - ((j - 1) % 64))
 	bitmap := c.bitmap()
+	n := c.N()
 	if x == y {
-		c.n -= int32(popcount(bitmap[x] & (X & Y)))
+		n -= int32(popcount(bitmap[x] & (X & Y)))
 		bitmap[x] &= ^(X & Y)
 	} else {
-		c.n -= int32(popcount(bitmap[x] & X))
+		n -= int32(popcount(bitmap[x] & X))
 		bitmap[x] &= ^X
 		for i := x + 1; i < y; i++ {
-			c.n -= int32(popcount(bitmap[i]))
+			n -= int32(popcount(bitmap[i]))
 			bitmap[i] = 0
 		}
-		c.n -= int32(popcount(bitmap[y] & Y))
+		n -= int32(popcount(bitmap[y] & Y))
 		bitmap[y] &= ^Y
 	}
+	c.setN(n)
 }
 
+// equals reports whether two containers are equal.
 func (c *Container) equals(c2 *Container) bool {
-	if c.mapped != c2.mapped || c.typ != c2.typ || c.n != c2.n {
+	if c == nil || c2 == nil {
+		if c != c2 {
+			return false
+		}
+	}
+	if c.Mapped() != c2.Mapped() || c.typ() != c2.typ() || c.N() != c2.N() {
 		return false
 	}
-	if c.typ == containerArray {
+	if c.typ() == containerArray {
 		ca, c2a := c.array(), c2.array()
 		if len(ca) != len(c2a) {
 			return false
@@ -3009,7 +3258,7 @@ func (c *Container) equals(c2 *Container) bool {
 				return false
 			}
 		}
-	} else if c.typ == containerBitmap {
+	} else if c.typ() == containerBitmap {
 		cb, c2b := c.bitmap(), c2.bitmap()
 		if len(cb) != len(c2b) {
 			return false
@@ -3019,7 +3268,7 @@ func (c *Container) equals(c2 *Container) bool {
 				return false
 			}
 		}
-	} else if c.typ == containerRun {
+	} else if c.typ() == containerRun {
 		cr, c2r := c.runs(), c2.runs()
 		if len(cr) != len(c2r) {
 			return false
@@ -3030,7 +3279,7 @@ func (c *Container) equals(c2 *Container) bool {
 			}
 		}
 	} else {
-		panic(fmt.Sprintf("unknown container type: %v", c.typ))
+		panic(fmt.Sprintf("unknown container type: %v", c.typ()))
 	}
 	return true
 }
@@ -3038,23 +3287,26 @@ func (c *Container) equals(c2 *Container) bool {
 func unionArrayBitmap(a, b *Container) *Container {
 	output := b.Clone()
 	bitmap := output.bitmap()
+	n := output.N()
 	for _, v := range a.array() {
 		if !output.bitmapContains(v) {
 			bitmap[v/64] |= (1 << uint64(v%64))
-			output.n++
+			n++
 		}
 	}
+	output.setN(n)
 	return output
 }
 
 // unions array b into bitmap a, mutating a in place. The n value
 // of a will need to be repaired after the fact.
-func unionBitmapArrayInPlace(a, b *Container) {
-	a.unmapBitmap()
+func unionBitmapArrayInPlace(a, b *Container) *Container {
+	a = a.Thaw()
 	bitmap := a.bitmap()
 	for _, v := range b.array() {
 		bitmap[v>>6] |= (uint64(1) << (v % 64))
 	}
+	return a
 }
 
 func unionBitmapBitmap(a, b *Container) *Container {
@@ -3074,15 +3326,14 @@ func unionBitmapBitmap(a, b *Container) *Container {
 		n += int32(popcount(ob[i]))
 	}
 
-	output := NewContainerBitmap(n, ob)
+	output := NewContainerBitmapN(ob, n)
 	return output
 }
 
 // unions bitmap b into bitmap a, mutating a in place. The n value of
 // a will need to be repaired after the fact.
-func unionBitmapBitmapInPlace(a, b *Container) {
-
-	a.unmapBitmap()
+func unionBitmapBitmapInPlace(a, b *Container) *Container {
+	a = a.Thaw()
 
 	// local variables added to prevent BCE checks in loop
 	// see https://go101.org/article/bounds-check-elimination.html
@@ -3099,9 +3350,16 @@ func unionBitmapBitmapInPlace(a, b *Container) {
 		ab[i+2] |= bb[i+2]
 		ab[i+3] |= bb[i+3]
 	}
+	return a
 }
 
 func difference(a, b *Container) *Container {
+	if a.N() == 0 || b.N() == maxContainerVal+1 {
+		return nil
+	}
+	if b.N() == 0 {
+		return a.Freeze()
+	}
 	if a.isArray() {
 		if b.isArray() {
 			return differenceArrayArray(a, b)
@@ -3160,12 +3418,7 @@ func differenceArrayArray(a, b *Container) *Container {
 func differenceArrayRun(a, b *Container) *Container {
 	statsHit("difference/ArrayRun")
 	// func (ac *arrayContainer) iandNotRun16(rc *runContainer16) container {
-
-	if a.n == 0 || b.n == 0 {
-		return a.Clone()
-	}
-
-	output := NewContainerArray(make([]uint16, 0, a.n))
+	output := make([]uint16, 0, a.N())
 	// cardinality upper bound: card(A)
 
 	i := 0 // array index
@@ -3173,11 +3426,11 @@ func differenceArrayRun(a, b *Container) *Container {
 	aa, rb := a.array(), b.runs()
 
 	// handle overlap
-	for i < int(a.n) {
+	for i < len(aa) {
 
 		// keep all array elements before beginning of runs
 		if aa[i] < rb[j].start {
-			output.add(aa[i])
+			output = append(output, aa[i])
 			i++
 			continue
 		}
@@ -3201,29 +3454,14 @@ func differenceArrayRun(a, b *Container) *Container {
 		// keep all array elements after end of runs
 		// It's possible that output was converted from array to bitmap in output.add()
 		// so check container type before proceeding.
-		if output.typ == containerArray {
-			array := output.array()
-			array = append(array, aa[i:]...)
-			output.setArray(array)
-			// TODO: consider handling container.n mutations in one place
-			// like we do with container.add().
-			output.n += int32(len(aa[i:]))
-		} else {
-			for _, v := range aa[i:] {
-				output.add(v)
-			}
-		}
+		output = append(output, aa[i:]...)
 	}
-	return output
+	return NewContainerArray(output)
 }
 
 // differenceBitmapRun computes the difference of an bitmap from a run.
 func differenceBitmapRun(a, b *Container) *Container {
 	statsHit("difference/BitmapRun")
-	if a.n == 0 || b.n == 0 {
-		return a.Clone()
-	}
-
 	output := a.Clone()
 	for _, run := range b.runs() {
 		output.bitmapZeroRange(uint64(run.start), uint64(run.last)+1)
@@ -3235,9 +3473,6 @@ func differenceBitmapRun(a, b *Container) *Container {
 // container.
 func differenceRunArray(a, b *Container) *Container {
 	statsHit("difference/RunArray")
-	if a.n == 0 || b.n == 0 {
-		return a.Clone()
-	}
 	ra, ab := a.runs(), b.array()
 	runs := make([]interval16, 0, len(ra))
 
@@ -3296,18 +3531,12 @@ func differenceRunBitmap(a, b *Container) *Container {
 	if len(ra) > 0 && ra[0].start == 0 && ra[0].last == 65535 {
 		return flipBitmap(b)
 	}
-	output := NewContainerRun(nil)
-	runs := output.runs()
-	if len(ra) == 0 {
-		return NewContainerRun(nil)
-	}
-	output.n = a.n
+	runs := make([]interval16, 0, len(ra))
 	for _, inputRun := range ra {
 		run := inputRun
 		add := true
 		for bit := inputRun.start; bit <= inputRun.last; bit++ {
 			if b.bitmapContains(bit) {
-				output.n--
 				if run.start == bit {
 					if bit == 65535 { //overflow
 						add = false
@@ -3340,11 +3569,11 @@ func differenceRunBitmap(a, b *Container) *Container {
 		}
 	}
 
-	output.setRuns(runs)
-	if output.n < ArrayMaxSize && int32(len(runs)) > output.n/2 {
-		output.runToArray()
+	output := NewContainerRun(runs)
+	if output.N() < ArrayMaxSize && int32(len(runs)) > output.N()/2 {
+		output = output.runToArray()
 	} else if len(runs) > runMaxSize {
-		output.runToBitmap()
+		output = output.runToBitmap()
 	}
 	return output
 }
@@ -3352,9 +3581,6 @@ func differenceRunBitmap(a, b *Container) *Container {
 // differenceRunRun computes the difference of two runs.
 func differenceRunRun(a, b *Container) *Container {
 	statsHit("difference/RunRun")
-	if a.n == 0 || b.n == 0 {
-		return a.Clone()
-	}
 
 	ra, rb := a.runs(), b.runs()
 	apos := 0 // current a-run index
@@ -3415,7 +3641,7 @@ func differenceRunRun(a, b *Container) *Container {
 
 func differenceArrayBitmap(a, b *Container) *Container {
 	statsHit("difference/ArrayBitmap")
-	output := make([]uint16, 0, a.n)
+	output := make([]uint16, 0, a.N())
 	bitmap := b.bitmap()
 	for _, va := range a.array() {
 		bmidx := va / 64
@@ -3435,14 +3661,16 @@ func differenceBitmapArray(a, b *Container) *Container {
 	output := a.Clone()
 	bitmap := output.bitmap()
 
+	n := output.N()
 	for _, v := range b.array() {
 		if output.bitmapContains(v) {
 			bitmap[v/64] &^= (uint64(1) << uint(v%64))
-			output.n--
+			n--
 		}
 	}
-	if output.n < ArrayMaxSize {
-		output.bitmapToArray()
+	output.setN(n)
+	if n < ArrayMaxSize {
+		output = output.bitmapToArray()
 	}
 	return output
 }
@@ -3465,14 +3693,20 @@ func differenceBitmapBitmap(a, b *Container) *Container {
 		n += int32(popcount(ob[i]))
 	}
 
-	output := NewContainerBitmap(n, ob)
-	if output.n < ArrayMaxSize {
-		output.bitmapToArray()
+	output := NewContainerBitmapN(ob, n)
+	if output.N() < ArrayMaxSize {
+		output = output.bitmapToArray()
 	}
 	return output
 }
 
 func xor(a, b *Container) *Container {
+	if a.N() == 0 {
+		return b.Freeze()
+	}
+	if b.N() == 0 {
+		return a.Freeze()
+	}
 	if a.isArray() {
 		if b.isArray() {
 			return xorArrayArray(a, b)
@@ -3502,33 +3736,33 @@ func xor(a, b *Container) *Container {
 
 func xorArrayArray(a, b *Container) *Container {
 	statsHit("xor/ArrayArray")
-	output := NewContainerArray(nil)
+	output := make([]uint16, 0)
 	aa, ab := a.array(), b.array()
 	na, nb := len(aa), len(ab)
 	for i, j := 0, 0; i < na || j < nb; {
 		if i < na && j >= nb {
-			output.add(aa[i])
+			output = append(output, aa[i])
 			i++
 			continue
 		} else if i >= na && j < nb {
-			output.add(ab[j])
+			output = append(output, ab[j])
 			j++
 			continue
 		}
 
 		va, vb := aa[i], ab[j]
 		if va < vb {
-			output.add(va)
+			output = append(output, va)
 			i++
 		} else if va > vb {
-			output.add(vb)
+			output = append(output, vb)
 			j++
 		} else { //==
 			i++
 			j++
 		}
 	}
-	return output
+	return NewContainerArray(output)
 }
 
 func xorArrayBitmap(a, b *Container) *Container {
@@ -3536,16 +3770,16 @@ func xorArrayBitmap(a, b *Container) *Container {
 	output := b.Clone()
 	for _, v := range a.array() {
 		if b.bitmapContains(v) {
-			output.remove(v)
+			output, _ = output.remove(v)
 		} else {
-			output.add(v)
+			output, _ = output.add(v)
 		}
 	}
 
 	// It's possible that output was converted from bitmap to array in output.remove()
 	// so we only do this conversion if output is still a bitmap container.
-	if output.typ == containerBitmap && output.count() < ArrayMaxSize {
-		output.bitmapToArray()
+	if output.typ() == containerBitmap && output.count() < ArrayMaxSize {
+		output = output.bitmapToArray()
 	}
 
 	return output
@@ -3569,9 +3803,9 @@ func xorBitmapBitmap(a, b *Container) *Container {
 		n += int32(popcount(ob[i]))
 	}
 
-	output := NewContainerBitmap(n, ob)
-	if output.count() < ArrayMaxSize {
-		output.bitmapToArray()
+	output := NewContainerBitmapN(ob, n)
+	if n < ArrayMaxSize {
+		output = output.bitmapToArray()
 	}
 	return output
 }
@@ -3580,6 +3814,9 @@ func xorBitmapBitmap(a, b *Container) *Container {
 // the new container and a bool indicating whether a
 // carry bit was shifted out.
 func shift(c *Container) (*Container, bool) {
+	if c.N() == 0 {
+		return nil, false
+	}
 	if c.isArray() {
 		return shiftArray(c)
 	} else if c.isRun() {
@@ -3607,23 +3844,18 @@ func shiftArray(a *Container) (*Container, bool) {
 // shiftBitmap is a bitmap-specific implementation of shift().
 func shiftBitmap(a *Container) (*Container, bool) {
 	statsHit("shift/Bitmap")
-	carry := false
-	output := NewContainerBitmap(a.n, nil)
+	carry := uint64(0)
+	output := NewContainerBitmapN(nil, 0)
 	ba, bo := a.bitmap(), output.bitmap()
-	lastCarry := false
+	lastCarry := uint64(0)
 	for i, v := range ba {
-		carry = (v & (1 << 63)) != 0
-		v = v << 1
-		if lastCarry {
-			v |= 1
-		}
+		carry = v >> 63
+		v = v<<1 | lastCarry
 		bo[i] = v
 		lastCarry = carry
 	}
-	if carry {
-		output.n--
-	}
-	return output, carry
+	output.setN(a.N() - int32(carry))
+	return output, carry != 0
 }
 
 // shiftRun is a run-specific implementation of shift().
@@ -3905,6 +4137,7 @@ func xorArrayRun(a, b *Container) *Container {
 	var vb interval16
 	var va uint16
 	lastI, lastJ := -1, -1
+	n := int32((0))
 	for i, j := 0, 0; i < na || j < nb; {
 		if i < na && i != lastI {
 			va = aa[i]
@@ -3916,14 +4149,14 @@ func xorArrayRun(a, b *Container) *Container {
 		lastJ = j
 
 		if i < na && (j >= nb || va < vb.start) { //before
-			output.n += output.runAppendInterval(interval16{start: va, last: va})
+			n += output.runAppendInterval(interval16{start: va, last: va})
 			i++
 		} else if j < nb && (i >= na || va > vb.last) { //after
-			output.n += output.runAppendInterval(vb)
+			n += output.runAppendInterval(vb)
 			j++
 		} else if va > vb.start {
 			if va < vb.last {
-				output.n += output.runAppendInterval(interval16{start: vb.start, last: va - 1})
+				n += output.runAppendInterval(interval16{start: vb.start, last: va - 1})
 				i++
 				vb.start = va + 1
 
@@ -3931,12 +4164,12 @@ func xorArrayRun(a, b *Container) *Container {
 					j++
 				}
 			} else if va > vb.last {
-				output.n += output.runAppendInterval(vb)
+				n += output.runAppendInterval(vb)
 				j++
 			} else { // va == vb.last
 				vb.last--
 				if vb.start <= vb.last {
-					output.n += output.runAppendInterval(vb)
+					n += output.runAppendInterval(vb)
 				}
 				j++
 				i++
@@ -3954,10 +4187,11 @@ func xorArrayRun(a, b *Container) *Container {
 			i++
 		}
 	}
-	if output.n < ArrayMaxSize {
-		output.runToArray()
+	output.setN(n)
+	if n < ArrayMaxSize {
+		output = output.runToArray()
 	} else if len(output.runs()) > runMaxSize {
-		output.runToBitmap()
+		output = output.runToBitmap()
 	}
 	return output
 }
@@ -4061,18 +4295,13 @@ func xorRunRun(a, b *Container) *Container {
 	statsHit("xor/RunRun")
 	ra, rb := a.runs(), b.runs()
 	na, nb := len(ra), len(rb)
-	if na == 0 {
-		return b.Clone()
-	}
-	if nb == 0 {
-		return a.Clone()
-	}
 	output := NewContainerRun(nil)
 
 	lastI, lastJ := -1, -1
 
 	state := &xorstm{}
 
+	n := int32(0)
 	for i, j := 0, 0; i < na || j < nb; {
 		if i < na && lastI != i {
 			state.va = ra[i]
@@ -4087,7 +4316,7 @@ func xorRunRun(a, b *Container) *Container {
 
 		r1, ok := xorCompare(state)
 		if ok {
-			output.n += output.runAppendInterval(r1)
+			n += output.runAppendInterval(r1)
 		}
 		if !state.vaValid {
 			i++
@@ -4099,10 +4328,11 @@ func xorRunRun(a, b *Container) *Container {
 	}
 
 	l := len(output.runs())
-	if output.n < ArrayMaxSize && int32(l) > output.n/2 {
-		output.runToArray()
+	output.setN(n)
+	if n < ArrayMaxSize && int32(l) > n/2 {
+		output = output.runToArray()
 	} else if l > runMaxSize {
-		output.runToBitmap()
+		output = output.runToBitmap()
 	}
 	return output
 }
@@ -4289,13 +4519,13 @@ func readOffsets(b *Bitmap, data []byte, pos int, keyN uint32) error {
 		// Map byte slice directly to the container data.
 		citer.Next()
 		_, c := citer.Value()
-		switch c.typ {
+		switch c.typ() {
 		case containerArray:
-			c.setArray((*[0xFFFFFFF]uint16)(unsafe.Pointer(&data[offset]))[:c.n:c.n])
+			c.setArray((*[0xFFFFFFF]uint16)(unsafe.Pointer(&data[offset]))[:c.N():c.N()])
 		case containerBitmap:
 			c.setBitmap((*[0xFFFFFFF]uint64)(unsafe.Pointer(&data[offset]))[:bitmapN:bitmapN])
 		default:
-			return fmt.Errorf("unsupported container type %d", c.typ)
+			return fmt.Errorf("unsupported container type %d", c.typ())
 		}
 	}
 	return nil
@@ -4306,7 +4536,7 @@ func readWithRuns(b *Bitmap, data []byte, pos int, keyN uint32) {
 	for i := 0; i < int(keyN); i++ {
 		citer.Next()
 		_, c := citer.Value()
-		switch c.typ {
+		switch c.typ() {
 		case containerRun:
 			runCount := binary.LittleEndian.Uint16(data[pos : pos+runCountHeaderSize])
 			c.setRuns((*[0xFFFFFFF]interval16)(unsafe.Pointer(&data[pos+runCountHeaderSize]))[:runCount:runCount])
@@ -4317,8 +4547,8 @@ func readWithRuns(b *Bitmap, data []byte, pos int, keyN uint32) {
 			}
 			pos += int((runCount * interval16Size) + runCountHeaderSize)
 		case containerArray:
-			c.setArray((*[0xFFFFFFF]uint16)(unsafe.Pointer(&data[pos]))[:c.n:c.n])
-			pos += int(c.n * 2)
+			c.setArray((*[0xFFFFFFF]uint16)(unsafe.Pointer(&data[pos]))[:c.N():c.N()])
+			pos += int(c.N() * 2)
 		case containerBitmap:
 			c.setBitmap((*[0xFFFFFFF]uint64)(unsafe.Pointer(&data[pos]))[:bitmapN:bitmapN])
 			pos += bitmapN * 8
@@ -4373,9 +4603,9 @@ func (w handledIters) calculateSummaryStats(key uint64) containerUnionSummarySta
 
 		if key == currKey {
 			summary.c++
-			summary.n += int64(currContainer.n)
+			summary.n += int64(currContainer.N())
 
-			if currContainer.n == maxContainerVal+1 {
+			if currContainer.N() == maxContainerVal+1 {
 				summary.hasMaxRange = true
 				summary.n = maxContainerVal + 1
 				return summary
diff --git a/row.go b/row.go
index a2e93843..79c91831 100644
--- a/row.go
+++ b/row.go
@@ -57,6 +57,12 @@ func (r *Row) IsEmpty() bool {
 	return true
 }
 
+func (r *Row) Freeze() {
+	for _, s := range r.segments {
+		s.Freeze()
+	}
+}
+
 // Merge merges data from other into r.
 func (r *Row) Merge(other *Row) {
 	var segments []rowSegment
@@ -210,15 +216,6 @@ func (r *Row) SetBit(i uint64) (changed bool) {
 	return r.createSegmentIfNotExists(i / ShardWidth).SetBit(i)
 }
 
-// clearBit clears the i-th column of the row.
-func (r *Row) clearBit(i uint64) (changed bool) { // nolint: unparam
-	s := r.segment(i / ShardWidth)
-	if s == nil {
-		return false
-	}
-	return s.ClearBit(i)
-}
-
 // Segments returns a list of all segments in the row.
 func (r *Row) Segments() []rowSegment {
 	return r.segments
@@ -246,12 +243,12 @@ func (r *Row) createSegmentIfNotExists(shard uint64) *rowSegment {
 	}
 
 	// Insert new segment.
-	r.segments = append(r.segments, rowSegment{data: *roaring.NewBitmap()})
+	r.segments = append(r.segments, rowSegment{data: roaring.NewSliceBitmap()})
 	if i < len(r.segments) {
 		copy(r.segments[i+1:], r.segments[i:])
 	}
 	r.segments[i] = rowSegment{
-		data:     *roaring.NewBitmap(),
+		data:     roaring.NewSliceBitmap(),
 		shard:    shard,
 		writable: true,
 	}
@@ -312,13 +309,17 @@ type rowSegment struct {
 	// Underlying raw bitmap implementation.
 	// This is an mmapped bitmap if writable is false. Otherwise
 	// it is a heap allocated bitmap which can be manipulated.
-	data     roaring.Bitmap
+	data     *roaring.Bitmap
 	writable bool
 
 	// Bit count
 	n uint64
 }
 
+func (s *rowSegment) Freeze() {
+	s.data.Freeze()
+}
+
 // Merge adds chunks from other to s.
 // Chunks in s are overwritten if they exist in other.
 func (s *rowSegment) Merge(other *rowSegment) {
@@ -332,50 +333,58 @@ func (s *rowSegment) Merge(other *rowSegment) {
 
 // IntersectionCount returns the number of intersections between s and other.
 func (s *rowSegment) IntersectionCount(other *rowSegment) uint64 {
-	return s.data.IntersectionCount(&other.data)
+	return s.data.IntersectionCount(other.data)
 }
 
 // Intersect returns the itersection of s and other.
 func (s *rowSegment) Intersect(other *rowSegment) *rowSegment {
-	data := s.data.Intersect(&other.data)
+	data := s.data.Intersect(other.data)
+	data.Freeze()
 
 	return &rowSegment{
-		data:  *data,
-		shard: s.shard,
-		n:     data.Count(),
+		data:     data,
+		shard:    s.shard,
+		n:        data.Count(),
+		writable: true,
 	}
 }
 
 // Union returns the bitwise union of s and other.
 func (s *rowSegment) Union(other *rowSegment) *rowSegment {
-	data := s.data.Union(&other.data)
+	data := s.data.Union(other.data)
+	data.Freeze()
 
 	return &rowSegment{
-		data:  *data,
-		shard: s.shard,
-		n:     data.Count(),
+		data:     data,
+		shard:    s.shard,
+		n:        data.Count(),
+		writable: true,
 	}
 }
 
 // Difference returns the diff of s and other.
 func (s *rowSegment) Difference(other *rowSegment) *rowSegment {
-	data := s.data.Difference(&other.data)
+	data := s.data.Difference(other.data)
+	data.Freeze()
 
 	return &rowSegment{
-		data:  *data,
-		shard: s.shard,
-		n:     data.Count(),
+		data:     data,
+		shard:    s.shard,
+		n:        data.Count(),
+		writable: true,
 	}
 }
 
 // Xor returns the xor of s and other.
 func (s *rowSegment) Xor(other *rowSegment) *rowSegment {
-	data := s.data.Xor(&other.data)
+	data := s.data.Xor(other.data)
+	data.Freeze()
 
 	return &rowSegment{
-		data:  *data,
-		shard: s.shard,
-		n:     data.Count(),
+		data:     data,
+		shard:    s.shard,
+		n:        data.Count(),
+		writable: true,
 	}
 }
 
@@ -386,11 +395,13 @@ func (s *rowSegment) Shift() (*rowSegment, error) {
 	if err != nil {
 		return nil, errors.Wrap(err, "shifting roaring data")
 	}
+	data.Freeze()
 
 	return &rowSegment{
-		data:  *data,
-		shard: s.shard,
-		n:     data.Count(),
+		data:     data,
+		shard:    s.shard,
+		n:        data.Count(),
+		writable: true,
 	}, nil
 }
 
@@ -439,7 +450,11 @@ func (s *rowSegment) ensureWritable() {
 		return
 	}
 
-	s.data = *s.data.Clone()
+	// This doesn't actually clone all the containers, but does clone
+	// the bitmap itself -- we get a new bitmap, but it just marks the
+	// containers as frozen and shares them. It's now safe to write to
+	// this bitmap, but the actual containers are copy-on-write.
+	s.data = s.data.Freeze()
 	s.writable = true
 }
 


Test patch:
diff --git a/fragment_internal_test.go b/fragment_internal_test.go
index ecc50681..d815f41b 100644
--- a/fragment_internal_test.go
+++ b/fragment_internal_test.go
@@ -34,6 +34,7 @@ import (
 	"github.com/davecgh/go-spew/spew"
 	"github.com/pilosa/pilosa/pql"
 	"github.com/pilosa/pilosa/roaring"
+	"github.com/pkg/errors"
 )
 
 // Test flags
@@ -3292,3 +3293,30 @@ func TestImportMultipleValues(t *testing.T) {
 		}
 	}
 }
+
+func TestFragmentConcurrentReadWrite(t *testing.T) {
+	f := mustOpenFragment("i", "f", viewStandard, 0, CacheTypeRanked)
+	defer f.Clean(t)
+
+	eg := &errgroup.Group{}
+	eg.Go(func() error {
+		for i := uint64(0); i < 1000; i++ {
+			_, err := f.setBit(i%4, i)
+			if err != nil {
+				return errors.Wrap(err, "setting bit")
+			}
+		}
+		return nil
+	})
+
+	acc := uint64(0)
+	for i := uint64(0); i < 100; i++ {
+		r := f.row(i % 4)
+		acc += r.Count()
+	}
+	if err := eg.Wait(); err != nil {
+		t.Errorf("error from setting a bit: %v", err)
+	}
+
+	t.Logf("%d", acc)
+}
diff --git a/roaring/btree_test.go b/roaring/btree_test.go
index c12892f6..422a7b76 100644
--- a/roaring/btree_test.go
+++ b/roaring/btree_test.go
@@ -467,13 +467,14 @@ func benchmarkSetRnd(b *testing.B, n int) {
 		a[i] = rng.Next()
 	}
 	b.ResetTimer()
+	c := getDummyC(1)
 	for i := 0; i < b.N; i++ {
 		b.StopTimer()
 		r := treeNew()
 		debug.FreeOSMemory()
 		b.StartTimer()
 		for _, v := range a {
-			r.Set(uint64(v), nil)
+			r.Set(uint64(v), c)
 		}
 		b.StopTimer()
 		r.Close()
@@ -504,8 +505,9 @@ func benchmarkGetRnd(b *testing.B, n int) {
 	for i := range a {
 		a[i] = rng.Next()
 	}
+	c := getDummyC(1)
 	for _, v := range a {
-		r.Set(uint64(v), nil)
+		r.Set(uint64(v), c)
 	}
 	debug.FreeOSMemory()
 	b.ResetTimer()
@@ -1392,7 +1394,7 @@ func TestBtreePut(t *testing.T) {
 					t.Fatal(iTest, g, e)
 				}
 			}
-			return nil, test.write
+			return getDummyC(99), test.write
 		})
 		if test.exists {
 			if g, e := oldV, getDummyC(test.oldV); g != e {
@@ -1427,6 +1429,8 @@ func TestBtreePut(t *testing.T) {
 			var e *Container
 			if test.post[i+1] != -1 {
 				e = getDummyC(test.post[i+1])
+			} else {
+				e = getDummyC(99)
 			}
 			if g := v; g != e {
 				t.Fatal(iTest, g, e)
@@ -1445,7 +1449,7 @@ func TestBtreeSeek(t *testing.T) {
 	tr := treeNew()
 	for i := 0; i < N; i++ {
 		k := 2*i + 1
-		tr.Set(uint64(k), nil)
+		tr.Set(uint64(k), getDummyC(1))
 	}
 	for i := 0; i < N; i++ {
 		k := 2 * i
@@ -1476,14 +1480,14 @@ func TestBtreePR4(t *testing.T) {
 	tr := treeNew()
 	for i := 0; i < 2*kd+1; i++ {
 		k := 1000 * i
-		tr.Set(uint64(k), nil)
+		tr.Set(uint64(k), getDummyC(1))
 	}
 	tr.Delete(1000 * kd)
 	for i := 0; i < kd; i++ {
-		tr.Set(uint64(1000*(kd+1)-1-i), nil)
+		tr.Set(uint64(1000*(kd+1)-1-i), getDummyC(1))
 	}
 	k := 1000*(kd+1) - 1 - kd
-	tr.Set(uint64(k), nil)
+	tr.Set(uint64(k), getDummyC(1))
 	if _, ok := tr.Get(uint64(k)); !ok {
 		t.Fatalf("key lost: %v", k)
 	}
diff --git a/roaring/containers_test.go b/roaring/containers_test.go
index ad95f2f7..abe5dbd9 100644
--- a/roaring/containers_test.go
+++ b/roaring/containers_test.go
@@ -43,14 +43,14 @@ func testContainersIterator(cs Containers, t *testing.T) {
 	if !itr.Next() {
 		t.Fatalf("one should be next, but got false")
 	}
-	if key, val := itr.Value(); key != 1 || val.n != 1 {
-		t.Fatalf("Wrong k/v, exp: 1,1 got: %v,%v", key, val.n)
+	if key, val := itr.Value(); key != 1 || val.N() != 1 {
+		t.Fatalf("Wrong k/v, exp: 1,1 got: %v,%v", key, val.N())
 	}
 	if !itr.Next() {
 		t.Fatalf("two should be next, but got false")
 	}
-	if key, val := itr.Value(); key != 2 || val.n != 2 {
-		t.Fatalf("Wrong k/v, exp: 2,2 got: %v,%v", key, val.n)
+	if key, val := itr.Value(); key != 2 || val.N() != 2 {
+		t.Fatalf("Wrong k/v, exp: 2,2 got: %v,%v", key, val.N())
 	}
 
 	if itr.Next() {
@@ -68,14 +68,14 @@ func testContainersIterator(cs Containers, t *testing.T) {
 	if !found {
 		t.Fatalf("should have found 3")
 	}
-	if key, val := itr.Value(); key != 3 || val.n != 3 {
-		t.Fatalf("Wrong k/v, exp: 3,3 got: %v,%v", key, val.n)
+	if key, val := itr.Value(); key != 3 || val.N() != 3 {
+		t.Fatalf("Wrong k/v, exp: 3,3 got: %v,%v", key, val.N())
 	}
 	if !itr.Next() {
 		t.Fatalf("5 should be next, but got false")
 	}
-	if key, val := itr.Value(); key != 5 || val.n != 5 {
-		t.Fatalf("Wrong k/v, exp: 5,5 got: %v,%v", key, val.n)
+	if key, val := itr.Value(); key != 5 || val.N() != 5 {
+		t.Fatalf("Wrong k/v, exp: 5,5 got: %v,%v", key, val.N())
 	}
 
 	itr, found = cs.Iterator(4)
@@ -85,14 +85,14 @@ func testContainersIterator(cs Containers, t *testing.T) {
 	if !itr.Next() {
 		t.Fatalf("5 should be next, but got false")
 	}
-	if key, val := itr.Value(); key != 5 || val.n != 5 {
-		t.Fatalf("Wrong k/v, exp: 5,5 got: %v,%v", key, val.n)
+	if key, val := itr.Value(); key != 5 || val.N() != 5 {
+		t.Fatalf("Wrong k/v, exp: 5,5 got: %v,%v", key, val.N())
 	}
 	if !itr.Next() {
 		t.Fatalf("6 should be next, but got false")
 	}
-	if key, val := itr.Value(); key != 6 || val.n != 6 {
-		t.Fatalf("Wrong k/v, exp: 6,6 got: %v,%v", key, val.n)
+	if key, val := itr.Value(); key != 6 || val.N() != 6 {
+		t.Fatalf("Wrong k/v, exp: 6,6 got: %v,%v", key, val.N())
 	}
 
 	if itr.Next() {
diff --git a/roaring/roaring_helpers_test.go b/roaring/roaring_helpers_test.go
index 8c8bbd9a..41d4059f 100644
--- a/roaring/roaring_helpers_test.go
+++ b/roaring/roaring_helpers_test.go
@@ -253,8 +253,7 @@ func doContainer(typ byte, data interface{}) *Container {
 	case containerArray:
 		return NewContainerArray(data.([]uint16))
 	case containerBitmap:
-		c := NewContainerBitmap(0, data.([]uint64))
-		c.n = c.count()
+		c := NewContainerBitmap(-1, data.([]uint64))
 		return c
 	case containerRun:
 		return NewContainerRun(data.([]interval16))
diff --git a/roaring/roaring_internal_test.go b/roaring/roaring_internal_test.go
index 8c3e7a93..95c8d1b0 100644
--- a/roaring/roaring_internal_test.go
+++ b/roaring/roaring_internal_test.go
@@ -32,10 +32,6 @@ func (iv interval16) String() string {
 	return fmt.Sprintf("[%d, %d]", iv.start, iv.last)
 }
 
-func (c *Container) String() string {
-	return fmt.Sprintf("<%s container  n=%d, array[%d], runs[%d], bitmap[%d]> type:%s", c.info().Type, c.n, len(c.array()), len(c.runs()), len(c.bitmap()), containerTypeNames[c.typ])
-}
-
 func TestRunAppendInterval(t *testing.T) {
 	a := NewContainerRun(nil)
 	tests := []struct {
@@ -102,15 +98,15 @@ func TestContainerRunAdd(t *testing.T) {
 		{8, []interval16{{start: 0, last: 4}, {start: 6, last: 8}, {start: 10, last: 10}}},
 	}
 	for _, test := range tests {
-		c.mapped = true
-		ret := c.add(test.op)
-		if !ret {
+		c.setMapped(true)
+		c, changed := c.add(test.op)
+		if !changed {
 			t.Fatalf("result of adding new bit should be true: %v", c.runs())
 		}
 		if !reflect.DeepEqual(c.runs(), test.exp) {
 			t.Fatalf("Should have %v, but got %v after adding %v", test.exp, c.runs(), test.op)
 		}
-		if c.mapped {
+		if c.Mapped() {
 			t.Fatalf("container should not be mapped after adding bit %v", test.op)
 		}
 	}
@@ -118,14 +114,14 @@ func TestContainerRunAdd(t *testing.T) {
 
 func TestContainerRunAdd2(t *testing.T) {
 	c := NewContainerRun(nil)
-	ret := c.add(0)
+	c, ret := c.add(0)
 	if !ret {
 		t.Fatalf("result of adding new bit should be true: %v", c.runs())
 	}
 	if !reflect.DeepEqual(c.runs(), []interval16{{start: 0, last: 0}}) {
 		t.Fatalf("should have 1 run of length 1, but have %v", c.runs())
 	}
-	ret = c.add(0)
+	c, ret = c.add(0)
 	if ret {
 		t.Fatalf("result of adding existing bit should be false: %v", c.runs())
 	}
@@ -237,23 +233,23 @@ func TestBitmapCountRange(t *testing.T) {
 }
 
 func TestIntersectionCountArrayBitmap3(t *testing.T) {
-	a, b := NewContainerBitmap(maxContainerVal+1, getFullBitmap()), NewContainerBitmap(maxContainerVal+1, getFullBitmap())
+	a, b := NewContainerBitmapN(getFullBitmap(), maxContainerVal+1), NewContainerBitmapN(getFullBitmap(), maxContainerVal+1)
 
 	res := intersectBitmapBitmap(a, b)
-	if res.n != res.count() || res.n != maxContainerVal+1 {
-		t.Fatalf("test #1 intersectCountBitmapBitmap fail orig: %v new: %v exp: %v", res.n, res.count(), maxContainerVal+1)
+	if res.N() != res.count() || res.N() != maxContainerVal+1 {
+		t.Fatalf("test #1 intersectCountBitmapBitmap fail orig: %v new: %v exp: %v", res.N(), res.count(), maxContainerVal+1)
 	}
 
-	a.bitmapToRun(0)
+	a = a.bitmapToRun(0)
 	res = intersectBitmapRun(b, a)
-	if res.n != res.count() || res.n != maxContainerVal+1 {
-		t.Fatalf("test #2 intersectCountBitmapRun fail orig: %v new: %v exp: %v", res.n, res.count(), maxContainerVal+1)
+	if res.N() != res.count() || res.N() != maxContainerVal+1 {
+		t.Fatalf("test #2 intersectCountBitmapRun fail orig: %v new: %v exp: %v", res.N(), res.count(), maxContainerVal+1)
 	}
 	b.bitmapToRun(0)
 	res = intersectRunRun(a, b)
 	n := intersectionCountRunRun(a, b)
-	if res.n != res.count() || res.n != maxContainerVal+1 || res.n != int32(n) {
-		t.Fatalf("test #3 intersectCountRunRun fail orig: %v new: %v exp: %v", res.n, res.count(), maxContainerVal+1)
+	if res.N() != res.count() || res.N() != maxContainerVal+1 || res.N() != int32(n) {
+		t.Fatalf("test #3 intersectCountRunRun fail orig: %v new: %v exp: %v", res.N(), res.count(), maxContainerVal+1)
 	}
 }
 
@@ -321,15 +317,16 @@ func TestRunRemove(t *testing.T) {
 	}
 
 	for i, test := range tests {
-		c.mapped = true
-		ret := c.remove(test.op)
+		c = c.Freeze()
+		var ret bool
+		c, ret = c.remove(test.op)
 		if ret != test.expRet || !reflect.DeepEqual(c.runs(), test.exp) {
 			t.Fatalf("test #%v Unexpected result removing %v from runs. Expected %v, got %v. Expected %v, got %v", i, test.op, test.expRet, ret, test.exp, c.runs())
 		}
-		if ret && c.mapped {
+		if ret && c.frozen() {
 			t.Fatalf("test #%v container was not unmapped although bit %v was removed", i, test.op)
 		}
-		if !ret && !c.mapped {
+		if !ret && !c.frozen() {
 			t.Fatalf("test #%v container was unmapped although bit %v was not removed", i, test.op)
 		}
 	}
@@ -370,7 +367,7 @@ func TestIntersectionCountBitmapRun(t *testing.T) {
 		t.Fatalf("count of %v with %v should be 1, but got %v", a.bitmap(), b.runs(), ret)
 	}
 
-	a = NewContainerBitmap(29, []uint64{0xF0000001, 0xFF00000000000000, 0xFF000000000000F0, 0x0F0000})
+	a = NewContainerBitmap(-1, []uint64{0xF0000001, 0xFF00000000000000, 0xFF000000000000F0, 0x0F0000})
 	b = NewContainerRun([]interval16{{start: 29, last: 31}, {start: 125, last: 134}, {start: 191, last: 197}, {start: 200, last: 300}})
 
 	ret = intersectionCountBitmapRun(a, b)
@@ -380,8 +377,6 @@ func TestIntersectionCountBitmapRun(t *testing.T) {
 }
 
 func TestIntersectionCountRunRun(t *testing.T) {
-	a := NewContainerRun(nil)
-	b := NewContainerRun(nil)
 	tests := []struct {
 		aruns []interval16
 		bruns []interval16
@@ -419,10 +414,8 @@ func TestIntersectionCountRunRun(t *testing.T) {
 			bruns: []interval16{{start: 9, last: 9}, {start: 11, last: 17}}, exp: 6},
 	}
 	for i, test := range tests {
-		a.typ = containerRun
-		b.typ = containerRun
-		a.setRuns(test.aruns)
-		b.setRuns(test.bruns)
+		a := NewContainerRun(test.aruns)
+		b := NewContainerRun(test.bruns)
 		ret := intersectionCountRunRun(a, b)
 		if ret != test.exp {
 			t.Fatalf("test #%v failed intersecting %v with %v should be %v, but got %v", i, test.aruns, test.bruns, test.exp, ret)
@@ -524,8 +517,8 @@ func TestIntersectRunRun(t *testing.T) {
 		a.setRuns(test.aruns)
 		b.setRuns(test.bruns)
 		ret := intersectRunRun(a, b)
-		if ret.n != test.expN {
-			t.Fatalf("test #%v expected n to be %v, but got %v", i, test.expN, ret.n)
+		if ret.N() != test.expN {
+			t.Fatalf("test #%v expected n to be %v, but got %v", i, test.expN, ret.N())
 		}
 		if test.exp != nil {
 			if !reflect.DeepEqual(ret.runs(), test.exp) {
@@ -538,8 +531,6 @@ func TestIntersectRunRun(t *testing.T) {
 }
 
 func TestIntersectBitmapRunBitmap(t *testing.T) {
-	a := NewContainerBitmap(0, nil)
-	b := NewContainerRun(nil)
 	tests := []struct {
 		bitmap []uint64
 		runs   []interval16
@@ -578,13 +569,11 @@ func TestIntersectBitmapRunBitmap(t *testing.T) {
 		},
 	}
 	for i, test := range tests {
-		copy(a.bitmap(), test.bitmap)
-		b.setRuns(test.runs)
-		b.n = 4097 // ;)
 		exp := make([]uint64, bitmapN)
 		copy(exp, test.exp)
-		a.typ = containerBitmap
-		b.typ = containerRun
+		a := NewContainerBitmap(-1, test.bitmap)
+		b := NewContainerRun(test.runs)
+		b.setN(4097)
 		ret := intersectBitmapRun(a, b)
 		if ret.isArray() {
 			ret.arrayToBitmap()
@@ -592,8 +581,8 @@ func TestIntersectBitmapRunBitmap(t *testing.T) {
 		if !reflect.DeepEqual(ret.bitmap(), exp) {
 			t.Fatalf("test #%v expected %v, but got %v", i, exp, ret.bitmap())
 		}
-		if ret.n != test.expN {
-			t.Fatalf("test #%v expected n to be %v, but got %v", i, test.expN, ret.n)
+		if ret.N() != test.expN {
+			t.Fatalf("test #%v expected n to be %v, but got %v", i, test.expN, ret.N())
 		}
 	}
 
@@ -646,8 +635,8 @@ func TestIntersectBitmapRunArray(t *testing.T) {
 		if !reflect.DeepEqual(ret.array(), test.exp) {
 			t.Fatalf("test #%v expected %v, but got %v", i, test.exp, ret.array())
 		}
-		if ret.n != test.expN {
-			t.Fatalf("test #%v expected n to be %v, but got %v", i, test.expN, ret.n)
+		if ret.N() != test.expN {
+			t.Fatalf("test #%v expected n to be %v, but got %v", i, test.expN, ret.N())
 		}
 	}
 
@@ -738,8 +727,7 @@ func TestDifferenceMixed(t *testing.T) {
 
 	b := NewContainerArray([]uint16{0, 2, 4, 6, 8, 10, 12})
 
-	c := NewContainerBitmap(0, MakeBitmap([]uint64{0x64}))
-	c.n = c.countRange(0, 100)
+	c := NewContainerBitmap(-1, MakeBitmap([]uint64{0x64}))
 
 	d := NewContainerArray([]uint16{1, 3, 5, 7, 9, 11, 12})
 
@@ -780,13 +768,13 @@ func TestDifferenceMixed(t *testing.T) {
 	}
 
 	res = difference(b, b)
-	if res.n != 0 {
-		t.Fatalf("test #8 expected 0, but got %d", res.n)
+	if res.N() != 0 {
+		t.Fatalf("test #8 expected 0, but got %d", res.N())
 	}
 
 	res = difference(c, c)
-	if res.n != 0 {
-		t.Fatalf("test #9 expected 0, but got %d", res.n)
+	if res.N() != 0 {
+		t.Fatalf("test #9 expected 0, but got %d", res.N())
 	}
 
 	res = difference(d, b)
@@ -901,7 +889,6 @@ func TestUnionArrayRun(t *testing.T) {
 }
 
 func TestBitmapSetRange(t *testing.T) {
-	c := NewContainerBitmap(0, nil)
 	tests := []struct {
 		bitmap []uint64
 		start  uint64
@@ -926,21 +913,18 @@ func TestBitmapSetRange(t *testing.T) {
 	}
 
 	for i, test := range tests {
-		bitmap := c.bitmap()
-		copy(bitmap, test.bitmap)
-		c.n = c.countRange(0, 65535)
-		c.bitmapSetRange(bitmap, test.start, test.last+1)
+		c := NewContainerBitmap(-1, test.bitmap)
+		c.bitmapSetRange(test.start, test.last+1)
 		if !reflect.DeepEqual(c.bitmap()[:len(test.exp)], test.exp) {
 			t.Fatalf("test %#v expected %x, got %x", i, test.exp, c.bitmap()[:len(test.bitmap)])
 		}
-		if test.expN != c.n {
-			t.Fatalf("test #%v expected n to be %v, but got %v", i, test.expN, c.n)
+		if test.expN != c.N() {
+			t.Fatalf("test #%v expected n to be %v, but got %v", i, test.expN, c.N())
 		}
 	}
 }
 
 func TestArrayToBitmap(t *testing.T) {
-	a := NewContainerArray(nil)
 	tests := []struct {
 		array []uint16
 		exp   []uint64
@@ -958,19 +942,15 @@ func TestArrayToBitmap(t *testing.T) {
 	for i, test := range tests {
 		exp := make([]uint64, bitmapN)
 		copy(exp, test.exp)
-
-		a.setArray(test.array)
-		a.n = int32(len(test.array))
-		a.arrayToBitmap()
+		a := NewContainerArray(test.array)
+		a = a.arrayToBitmap()
 		if !reflect.DeepEqual(a.bitmap(), exp) {
 			t.Fatalf("test #%v expected %v, but got %v", i, exp, a.bitmap())
 		}
-		a.bitmapToArray()
 	}
 }
 
 func TestBitmapToArray(t *testing.T) {
-	a := NewContainerBitmap(0, nil)
 	tests := []struct {
 		bitmap []uint64
 		exp    []uint16
@@ -985,25 +965,16 @@ func TestBitmapToArray(t *testing.T) {
 		},
 	}
 	for i, test := range tests {
-		a.setBitmap(make([]uint64, bitmapN))
-		bitmap := a.bitmap()
-		n := int32(0)
-		for i, v := range test.bitmap {
-			bitmap[i] = v
-			n += int32(popcount(v))
-		}
-		a.n = n
+		a := NewContainerBitmap(-1, test.bitmap)
 
-		a.bitmapToArray()
+		a = a.bitmapToArray()
 		if !reflect.DeepEqual(a.array(), test.exp) {
 			t.Fatalf("test #%v expected %#v, but got %#v", i, test.exp, a.array())
 		}
-		a.arrayToBitmap()
 	}
 }
 
 func TestRunToBitmap(t *testing.T) {
-	a := NewContainerRun(nil)
 	tests := []struct {
 		runs []interval16
 		exp  []uint64
@@ -1037,11 +1008,8 @@ func TestRunToBitmap(t *testing.T) {
 			exp[i] = v
 			n += int(popcount(v))
 		}
-
-		a.typ = containerRun
-		a.setRuns(test.runs)
-		a.n = int32(n)
-		a.runToBitmap()
+		a := NewContainerRun(test.runs)
+		a = a.runToBitmap()
 		if !reflect.DeepEqual(a.bitmap(), exp) {
 			t.Fatalf("test #%v expected %v, but got %v", i, exp, a.bitmap())
 		}
@@ -1058,7 +1026,6 @@ func getFullBitmap() []uint64 {
 }
 
 func TestBitmapToRun(t *testing.T) {
-	a := NewContainerBitmap(0, nil)
 	tests := []struct {
 		bitmap []uint64
 		exp    []interval16
@@ -1116,15 +1083,8 @@ func TestBitmapToRun(t *testing.T) {
 	tests[8].bitmap[1023] = 0xFFFFFFFFFFFFFFFF
 
 	for i, test := range tests {
-		a.setBitmap(make([]uint64, bitmapN))
-		bitmap := a.bitmap()
-		n := 0
-		for i, v := range test.bitmap {
-			bitmap[i] = v
-			n += int(popcount(v))
-		}
-		a.n = int32(n)
-		x := bitmap
+		a := NewContainerBitmap(-1, test.bitmap)
+		x := a.bitmap()
 		a.bitmapToRun(0)
 		if !reflect.DeepEqual(a.runs(), test.exp) {
 			t.Fatalf("test #%v expected %v, but got %v", i, test.exp, a.runs())
@@ -1137,7 +1097,6 @@ func TestBitmapToRun(t *testing.T) {
 }
 
 func TestArrayToRun(t *testing.T) {
-	a := NewContainerArray(nil)
 	tests := []struct {
 		array []uint16
 		exp   []interval16
@@ -1161,10 +1120,8 @@ func TestArrayToRun(t *testing.T) {
 	}
 
 	for i, test := range tests {
-		a.typ = containerArray
-		a.setArray(test.array)
-		a.n = int32(len(test.array))
-		a.arrayToRun(0)
+		a := NewContainerArray(test.array)
+		a = a.arrayToRun(0)
 		if !reflect.DeepEqual(a.runs(), test.exp) {
 			t.Fatalf("test #%v expected %v, but got %v", i, test.exp, a.runs())
 		}
@@ -1172,7 +1129,6 @@ func TestArrayToRun(t *testing.T) {
 }
 
 func TestRunToArray(t *testing.T) {
-	a := NewContainerRun(nil)
 	tests := []struct {
 		runs []interval16
 		exp  []uint16
@@ -1196,10 +1152,8 @@ func TestRunToArray(t *testing.T) {
 	}
 
 	for i, test := range tests {
-		a.typ = containerRun
-		a.setRuns(test.runs)
-		a.n = int32(len(test.exp))
-		a.runToArray()
+		a := NewContainerRun(test.runs)
+		a = a.runToArray()
 		if !reflect.DeepEqual(a.array(), test.exp) {
 			t.Fatalf("test #%v expected %v, but got %v", i, test.exp, a.array())
 		}
@@ -1207,7 +1161,6 @@ func TestRunToArray(t *testing.T) {
 }
 
 func TestBitmapZeroRange(t *testing.T) {
-	c := NewContainerBitmap(0, nil)
 	tests := []struct {
 		bitmap []uint64
 		start  uint64
@@ -1230,17 +1183,16 @@ func TestBitmapZeroRange(t *testing.T) {
 			expN:   13,
 		},
 	}
-	bitmap := c.bitmap()
 
 	for i, test := range tests {
-		copy(bitmap, test.bitmap)
-		c.n = c.countRange(0, 65535)
+		c := NewContainerBitmap(-1, test.bitmap)
+		bitmap := c.bitmap()
 		c.bitmapZeroRange(test.start, test.last+1)
 		if !reflect.DeepEqual(bitmap[:len(test.exp)], test.exp) {
 			t.Fatalf("test %#v expected %x, got %x", i, test.exp, bitmap[:len(test.bitmap)])
 		}
-		if test.expN != c.n {
-			t.Fatalf("test #%v expected n to be %v, but got %v", i, test.expN, c.n)
+		if test.expN != c.N() {
+			t.Fatalf("test #%v expected n to be %v, but got %v", i, test.expN, c.N())
 		}
 		for i := range test.bitmap {
 			bitmap[i] = 0
@@ -1250,8 +1202,6 @@ func TestBitmapZeroRange(t *testing.T) {
 }
 
 func TestUnionBitmapRun(t *testing.T) {
-	a := NewContainerBitmap(0, nil)
-	b := NewContainerRun(nil)
 	tests := []struct {
 		bitmap []uint64
 		runs   []interval16
@@ -1266,20 +1216,18 @@ func TestUnionBitmapRun(t *testing.T) {
 		},
 	}
 	for i, test := range tests {
-		copy(a.bitmap(), test.bitmap)
-		a.n = a.bitmapCountRange(0, 65535)
-		b.setRuns(test.runs)
-		b.n = b.runCountRange(0, 65535)
+		a := NewContainerBitmap(-1, test.bitmap)
+		b := NewContainerRun(test.runs)
 		ret := unionBitmapRun(a, b)
 		if ret.isArray() {
-			ret.arrayToBitmap()
+			ret = ret.arrayToBitmap()
 		}
 		bitmap := ret.bitmap()
 		if !reflect.DeepEqual(bitmap[:len(test.exp)], test.exp) {
 			t.Fatalf("test #%v expected %x, but got %x", i, test.exp, bitmap[:len(test.exp)])
 		}
-		if ret.n != test.expN {
-			t.Fatalf("test #%v expected n to be %v, but got %v", i, test.expN, ret.n)
+		if ret.N() != test.expN {
+			t.Fatalf("test #%v expected n to be %v, but got %v", i, test.expN, ret.N())
 		}
 		for i := range test.bitmap {
 			a.bitmap()[i] = 0
@@ -1288,7 +1236,6 @@ func TestUnionBitmapRun(t *testing.T) {
 }
 
 func TestBitmapCountRuns(t *testing.T) {
-	c := NewContainerBitmap(0, nil)
 	tests := []struct {
 		bitmap []uint64
 		exp    int32
@@ -1310,10 +1257,10 @@ func TestBitmapCountRuns(t *testing.T) {
 			exp:    10,
 		},
 	}
+	var c *Container
 
 	for i, test := range tests {
-		copy(c.bitmap(), test.bitmap)
-
+		c = NewContainerBitmap(-1, test.bitmap)
 		ret := c.bitmapCountRuns()
 		if ret != test.exp {
 			t.Fatalf("test #%v expected %v but got %v", i, test.exp, ret)
@@ -1377,8 +1324,6 @@ func TestArrayCountRuns(t *testing.T) {
 }
 
 func TestDifferenceArrayRun(t *testing.T) {
-	a := NewContainerArray(nil)
-	b := NewContainerRun(nil)
 	tests := []struct {
 		array []uint16
 		runs  []interval16
@@ -1391,10 +1336,8 @@ func TestDifferenceArrayRun(t *testing.T) {
 		},
 	}
 	for i, test := range tests {
-		a.setArray(test.array)
-		a.n = int32(len(a.array()))
-		b.setRuns(test.runs)
-		b.n = b.runCountRange(0, 100)
+		a := NewContainerArray(test.array)
+		b := NewContainerRun(test.runs)
 		ret := differenceArrayRun(a, b)
 		if !reflect.DeepEqual(ret.array(), test.exp) {
 			t.Fatalf("test #%v expected %v, but got %v", i, test.exp, ret.array())
@@ -1403,8 +1346,6 @@ func TestDifferenceArrayRun(t *testing.T) {
 }
 
 func TestDifferenceRunArray(t *testing.T) {
-	a := NewContainerRun(nil)
-	b := NewContainerArray(nil)
 	tests := []struct {
 		runs  []interval16
 		array []uint16
@@ -1457,10 +1398,8 @@ func TestDifferenceRunArray(t *testing.T) {
 		},
 	}
 	for i, test := range tests {
-		a.setRuns(test.runs)
-		a.n = a.runCountRange(0, 100)
-		b.setArray(test.array)
-		b.n = int32(len(b.array()))
+		a := NewContainerRun(test.runs)
+		b := NewContainerArray(test.array)
 		ret := differenceRunArray(a, b)
 		if !reflect.DeepEqual(ret.runs(), test.exp) {
 			t.Fatalf("test #%v expected %v, but got %v", i, test.exp, ret.runs())
@@ -1480,8 +1419,6 @@ func MakeLastBitSet() []uint64 {
 }
 
 func TestDifferenceRunBitmap(t *testing.T) {
-	a := NewContainerRun(nil)
-	b := NewContainerBitmap(0, nil)
 	tests := []struct {
 		runs   []interval16
 		bitmap []uint64
@@ -1529,10 +1466,8 @@ func TestDifferenceRunBitmap(t *testing.T) {
 		},
 	}
 	for i, test := range tests {
-		a.setRuns(test.runs)
-		a.n = a.runCountRange(0, 65536)
-		copy(b.bitmap(), test.bitmap)
-		b.n = b.bitmapCountRange(0, 65536)
+		a := NewContainerRun(test.runs)
+		b := NewContainerBitmap(-1, test.bitmap)
 		ret := differenceRunBitmap(a, b)
 		if !reflect.DeepEqual(ret.runs(), test.exp) {
 			t.Fatalf("test #%v expected %v, but got %v", i, test.exp, ret.runs())
@@ -1541,8 +1476,6 @@ func TestDifferenceRunBitmap(t *testing.T) {
 }
 
 func TestDifferenceBitmapRun(t *testing.T) {
-	a := NewContainerBitmap(0, nil)
-	b := NewContainerRun(nil)
 	tests := []struct {
 		bitmap []uint64
 		runs   []interval16
@@ -1610,10 +1543,8 @@ func TestDifferenceBitmapRun(t *testing.T) {
 		},
 	}
 	for i, test := range tests {
-		copy(a.bitmap(), test.bitmap)
-		a.n = a.bitmapCountRange(0, 65536)
-		b.setRuns(test.runs)
-		b.n = b.runCountRange(0, 65536)
+		a := NewContainerBitmap(-1, test.bitmap)
+		b := NewContainerRun(test.runs)
 		ret := differenceBitmapRun(a, b)
 		if !reflect.DeepEqual(ret.bitmap()[:len(test.exp)], test.exp) {
 			t.Fatalf("test #%v expected \n%X, but got \n%X", i, test.exp, ret.bitmap()[:len(test.exp)])
@@ -1622,8 +1553,6 @@ func TestDifferenceBitmapRun(t *testing.T) {
 }
 
 func TestDifferenceBitmapArray(t *testing.T) {
-	b := NewContainerBitmap(0, nil)
-	a := NewContainerArray(nil)
 	tests := []struct {
 		bitmap []uint64
 		array  []uint16
@@ -1661,9 +1590,8 @@ func TestDifferenceBitmapArray(t *testing.T) {
 		},
 	}
 	for i, test := range tests {
-		b.bitmap()[0] = test.bitmap[0]
-		b.n = b.count()
-		a.setArray(test.array)
+		b := NewContainerBitmap(-1, test.bitmap[:1])
+		a := NewContainerArray(test.array)
 		ret := differenceBitmapArray(b, a)
 		if !reflect.DeepEqual(ret.array(), test.exp) {
 			t.Fatalf("test #%v expected %#v, but got %#v", i, test.exp, ret.array())
@@ -1672,8 +1600,6 @@ func TestDifferenceBitmapArray(t *testing.T) {
 }
 
 func TestDifferenceBitmapBitmap(t *testing.T) {
-	a := NewContainerBitmap(0, nil)
-	b := NewContainerBitmap(0, nil)
 	tests := []struct {
 		abitmap []uint64
 		bbitmap []uint64
@@ -1691,9 +1617,8 @@ func TestDifferenceBitmapBitmap(t *testing.T) {
 		},
 	}
 	for i, test := range tests {
-		a.bitmap()[0] = test.abitmap[0]
-		b.bitmap()[0] = test.bbitmap[0]
-
+		a := NewContainerBitmap(-1, test.abitmap)
+		b := NewContainerBitmap(-1, test.bbitmap)
 		ret := differenceBitmapBitmap(a, b)
 		if !reflect.DeepEqual(ret.array(), test.exp) {
 			t.Fatalf("test #%v expected \n%X, but got \n%X", i, test.exp, ret.array())
@@ -1702,8 +1627,6 @@ func TestDifferenceBitmapBitmap(t *testing.T) {
 }
 
 func TestDifferenceRunRun(t *testing.T) {
-	a := NewContainerRun(nil)
-	b := NewContainerRun(nil)
 	tests := []struct {
 		aruns []interval16
 		bruns []interval16
@@ -1721,16 +1644,14 @@ func TestDifferenceRunRun(t *testing.T) {
 		},
 	}
 	for i, test := range tests {
-		a.setRuns(test.aruns)
-		a.n = a.runCountRange(0, 100)
-		b.setRuns(test.bruns)
-		b.n = b.runCountRange(0, 100)
+		a := NewContainerRun(test.aruns)
+		b := NewContainerRun(test.bruns)
 		ret := differenceRunRun(a, b)
 		if !reflect.DeepEqual(ret.runs(), test.exp) {
 			t.Fatalf("test #%v expected %v, but got %v", i, test.exp, ret.runs())
 		}
-		if ret.n != test.expn {
-			t.Fatalf("test #%v expected n=%v, but got n=%v", i, test.expn, ret.n)
+		if ret.N() != test.expn {
+			t.Fatalf("test #%v expected n=%v, but got n=%v", i, test.expn, ret.N())
 		}
 	}
 }
@@ -1756,7 +1677,7 @@ func TestWriteReadArray(t *testing.T) {
 
 func TestWriteReadBitmap(t *testing.T) {
 	// create bitmap containing > 4096 bits
-	cb := NewContainerBitmap(129*32, nil)
+	cb := NewContainerBitmapN(nil, 129*32)
 	for i := 0; i < 129; i++ {
 		cb.bitmap()[i] = 0x5555555555555555
 	}
@@ -1779,7 +1700,7 @@ func TestWriteReadBitmap(t *testing.T) {
 
 func TestWriteReadFullBitmap(t *testing.T) {
 	// create bitmap containing > 4096 bits
-	cb := NewContainerBitmap(65536, nil)
+	cb := NewContainerBitmapN(nil, 65536)
 	for i := 0; i < bitmapN; i++ {
 		cb.bitmap()[i] = 0xffffffffffffffff
 	}
@@ -1802,11 +1723,11 @@ func TestWriteReadFullBitmap(t *testing.T) {
 		t.Fatalf("bitmap test expected %x, but got %x", cb.bitmap(), bb2.Containers.Get(0).bitmap())
 	}
 
-	if bb2.Containers.Get(0).n != cb.n {
-		t.Fatalf("bitmap test expected count %x, but got %x", cb.n, bb2.Containers.Get(0).n)
+	if bb2.Containers.Get(0).N() != cb.N() {
+		t.Fatalf("bitmap test expected count %x, but got %x", cb.N(), bb2.Containers.Get(0).N())
 	}
 	if bb2.Containers.Get(0).count() != cb.count() {
-		t.Fatalf("bitmap test expected count %x, but got %x", cb.n, bb2.Containers.Get(0).n)
+		t.Fatalf("bitmap test expected count %x, but got %x", cb.N(), bb2.Containers.Get(0).N())
 	}
 }
 
@@ -1855,8 +1776,8 @@ func TestXorArrayRun(t *testing.T) {
 	}
 
 	for i, test := range tests {
-		test.a.n = test.a.count()
-		test.b.n = test.b.count()
+		test.a.setN(test.a.count())
+		test.b.setN(test.b.count())
 		ret := xor(test.a, test.b)
 		if !reflect.DeepEqual(ret.array(), test.exp.array()) {
 			t.Fatalf("test #%v expected %#v, but got %#v", i, test.exp, ret)
@@ -1982,7 +1903,6 @@ func TestXorRunRun(t *testing.T) {
 }
 
 func TestBitmapXorRange(t *testing.T) {
-	c := NewContainerBitmap(0, nil)
 	tests := []struct {
 		bitmap []uint64
 		start  uint64
@@ -2035,14 +1955,13 @@ func TestBitmapXorRange(t *testing.T) {
 	}
 
 	for i, test := range tests {
-		copy(c.bitmap(), test.bitmap)
-		c.n = c.countRange(0, 65535)
+		c := NewContainerBitmap(-1, test.bitmap)
 		c.bitmapXorRange(test.start, test.last+1)
 		if !reflect.DeepEqual(c.bitmap()[:len(test.exp)], test.exp) {
 			t.Fatalf("test %#v expected %x, got %x", i, test.exp, c.bitmap()[:len(test.bitmap)])
 		}
-		if test.expN != c.n {
-			t.Fatalf("test #%v expected n to be %v, but got %v", i, test.expN, c.n)
+		if test.expN != c.N() {
+			t.Fatalf("test #%v expected n to be %v, but got %v", i, test.expN, c.N())
 		}
 	}
 }
@@ -2060,15 +1979,21 @@ func TestXorBitmapRun(t *testing.T) {
 		},
 	}
 	for i, test := range tests {
-		a := NewContainerBitmap(0, test.bitmap)
-		e := NewContainerBitmap(0, test.exp)
+		a := NewContainerBitmap(-1, test.bitmap)
+		e := NewContainerBitmap(-1, test.exp)
 		b := NewContainerRun(test.runs)
 		//xorBitmapRun
 		ret := xor(a, b)
+		if ret.isRun() {
+			ret = ret.runToBitmap()
+		}
 		if !reflect.DeepEqual(ret.bitmap(), e.bitmap()) {
 			t.Fatalf("test #%v expected %v, but got %v", i, e.bitmap(), ret.bitmap())
 		}
 		ret = xor(b, a)
+		if ret.isRun() {
+			ret = ret.runToBitmap()
+		}
 		if !reflect.DeepEqual(ret.bitmap(), e.bitmap()) {
 			t.Fatalf("test #%v.1 expected %v, but got %v", i, e.bitmap(), ret.bitmap())
 		}
@@ -2397,15 +2322,14 @@ func TestRunBinSearch(t *testing.T) {
 }
 func TestBitmap_RemoveEmptyContainers(t *testing.T) {
 	bm1 := NewFileBitmap(1<<16, 2<<16, 3<<16)
-	if _, err := bm1.Remove(2 << 16); err != nil {
-		t.Fatalf("removing a bit: %v", err)
-	}
-	if bm1.countEmptyContainers() != 1 {
+	bm2 := NewFileBitmap(1<<16, 2<<16+1, 3<<16)
+	bm3 := bm1.Intersect(bm2)
+	if bm3.countEmptyContainers() != 1 {
 		t.Fatalf("Should be 1 empty container ")
 	}
-	bm1.removeEmptyContainers()
+	bm3.removeEmptyContainers()
 
-	if bm1.countEmptyContainers() != 0 {
+	if bm3.countEmptyContainers() != 0 {
 		t.Fatalf("Should be no empty containers ")
 	}
 }
@@ -2510,7 +2434,6 @@ func TestSearch64(t *testing.T) {
 }
 
 func TestIntersectArrayBitmap(t *testing.T) {
-	a, b := NewContainerArray(nil), NewContainerBitmap(0, nil)
 	tests := []struct {
 		array  []uint16
 		bitmap []uint64
@@ -2554,8 +2477,8 @@ func TestIntersectArrayBitmap(t *testing.T) {
 	}
 
 	for i, test := range tests {
-		a.setArray(test.array)
-		copy(b.bitmap(), test.bitmap)
+		a := NewContainerArray(test.array)
+		b := NewContainerBitmap(-1, test.bitmap)
 		ret := intersectArrayBitmap(a, b).array()
 		if len(ret) == 0 && len(test.exp) == 0 {
 			continue
@@ -3274,42 +3197,48 @@ func TestContainerCombinations(t *testing.T) {
 				for _, ct := range containerTypes {
 					clone := ret.Clone()
 					if ct == containerArray {
-						if clone.isBitmap() {
-							clone.bitmapToArray()
+						if clone == nil {
+							clone = NewContainerArray(nil)
+						} else if clone.isBitmap() {
+							clone = clone.bitmapToArray()
 						} else if clone.isRun() {
-							clone.runToArray()
+							clone = clone.runToArray()
 						}
-						if clone.n != cts[ct][exp].n {
-							t.Fatalf("test %s expected array n=%d, but got n=%d", desc, cts[ct][exp].n, clone.n)
+						if clone.N() != cts[ct][exp].N() {
+							t.Errorf("test %s expected array n=%d, but got n=%d", desc, cts[ct][exp].N(), clone.N())
 						}
 						// Because xorRunRun resulting in an empty container returns an array container with a
 						// nil slice array, then we need to check len() on array first (look for 0).
 						if !(len(clone.array()) == 0 && len(cts[ct][exp].array()) == 0) && !reflect.DeepEqual(clone.array(), cts[ct][exp].array()) {
-							t.Fatalf("test %s expected array %X, but got %X", desc, cts[ct][exp].array(), clone.array())
+							t.Errorf("test %s expected array %X, but got %X", desc, cts[ct][exp].array(), clone.array())
 						}
 					} else if ct == containerBitmap {
-						if clone.isArray() {
-							clone.arrayToBitmap()
+						if clone == nil {
+							clone = NewContainerBitmap(0, nil)
+						} else if clone.isArray() {
+							clone = clone.arrayToBitmap()
 						} else if clone.isRun() {
-							clone.runToBitmap()
+							clone = clone.runToBitmap()
 						}
-						if clone.n != cts[ct][exp].n {
-							t.Fatalf("test %s expected bitmap n=%d, but got n=%d", desc, cts[ct][exp].n, clone.n)
+						if clone.N() != cts[ct][exp].N() {
+							t.Errorf("test %s expected bitmap n=%d, but got n=%d", desc, cts[ct][exp].N(), clone.N())
 						}
 						if !reflect.DeepEqual(clone.bitmap(), cts[ct][exp].bitmap()) {
-							t.Fatalf("test %s expected bitmap %X, but got %X", desc, cts[ct][exp].bitmap(), clone.bitmap())
+							t.Errorf("test %s expected bitmap %X, but got %X", desc, cts[ct][exp].bitmap(), clone.bitmap())
 						}
 					} else if ct == containerRun {
-						if clone.isArray() {
-							clone.arrayToRun(0)
+						if clone == nil {
+							clone = NewContainerRun(nil)
+						} else if clone.isArray() {
+							clone = clone.arrayToRun(0)
 						} else if clone.isBitmap() {
-							clone.bitmapToRun(0)
+							clone = clone.bitmapToRun(0)
 						}
-						if clone.n != cts[ct][exp].n {
-							t.Fatalf("test %s expected runs n=%d, but got n=%d", desc, cts[ct][exp].n, clone.n)
+						if clone.N() != cts[ct][exp].N() {
+							t.Errorf("test %s expected runs n=%d, but got n=%d", desc, cts[ct][exp].N(), clone.N())
 						}
 						if !reflect.DeepEqual(clone.runs(), cts[ct][exp].runs()) {
-							t.Fatalf("test %s expected runs %X, but got %X", desc, cts[ct][exp].runs(), clone.runs())
+							t.Errorf("test %s expected runs %X, but got %X", desc, cts[ct][exp].runs(), clone.runs())
 						}
 					}
 				}
@@ -3405,7 +3334,6 @@ func TestEquals(t *testing.T) {
 }
 */
 func TestShiftArray(t *testing.T) {
-	a := NewContainerArray(nil)
 	tests := []struct {
 		array []uint16
 		exp   []uint16
@@ -3429,10 +3357,16 @@ func TestShiftArray(t *testing.T) {
 	}
 
 	for i, test := range tests {
-		a.setArray(test.array)
-		a.n = int32(len(a.array()))
+		a := NewContainerArray(test.array)
 		ret1, _ := shift(a)      // test generic shift function
 		ret2, _ := shiftArray(a) // test array-specific shift function
+		// accept nil *Container as valid substitute for empty array
+		if ret1 == nil {
+			ret1 = NewContainerArray(nil)
+		}
+		if ret2 == nil {
+			ret2 = NewContainerArray(nil)
+		}
 		if !reflect.DeepEqual(ret1.array(), test.exp) {
 			t.Fatalf("test #%v shift() expected %v, but got %v", i, test.exp, ret1.array())
 		} else if !reflect.DeepEqual(ret2.array(), test.exp) {
@@ -3443,7 +3377,6 @@ func TestShiftArray(t *testing.T) {
 
 func TestShiftBitmap(t *testing.T) {
 	// note, bitmaps are provided for us by the ensuing tests
-	a := NewContainerBitmap(0, nil)
 	tests := []struct {
 		bitmap []uint64
 		exp    []uint64
@@ -3463,11 +3396,10 @@ func TestShiftBitmap(t *testing.T) {
 	}
 
 	for i, test := range tests {
-		a.setBitmap(test.bitmap)
-		a.n = 1
+		a := NewContainerBitmap(-1, test.bitmap)
 		ret1, _ := shift(a)       // test generic shift function
 		ret2, _ := shiftBitmap(a) // test bitmap-specific shift function
-		e := NewContainerBitmap(1, test.exp)
+		e := NewContainerBitmap(-1, test.exp)
 		if !reflect.DeepEqual(ret1.bitmap(), e.bitmap()) {
 			t.Fatalf("test #%v shift() expected %v, but got %v", i, e.bitmap(), ret1.bitmap())
 		} else if !reflect.DeepEqual(ret2.bitmap(), test.exp) {
@@ -3476,8 +3408,6 @@ func TestShiftBitmap(t *testing.T) {
 	}
 }
 func TestShiftRun(t *testing.T) {
-	a := NewContainerRun(nil)
-
 	tests := []struct {
 		runs  []interval16
 		n     int32
@@ -3509,14 +3439,13 @@ func TestShiftRun(t *testing.T) {
 	}
 
 	for i, test := range tests {
-		a.setRuns(test.runs)
-		a.n = test.n
+		a := NewContainerRun(test.runs)
 		ret1, c1 := shift(a)    // test generic shift function
 		ret2, c2 := shiftRun(a) // test run-specific shift function
-		if !reflect.DeepEqual(ret1.runs(), test.exp) && c1 == test.carry && ret1.n == test.en {
-			t.Fatalf("test #%v shift() expected %v, but got %v %d", i, test.exp, ret1.runs(), ret1.n)
-		} else if !reflect.DeepEqual(ret2.runs(), test.exp) && c2 == test.carry && ret2.n == test.en {
-			t.Fatalf("test #%v shiftRun() expected %v, but got %v %d", i, test.exp, ret2.runs(), ret2.n)
+		if !reflect.DeepEqual(ret1.runs(), test.exp) && c1 == test.carry && ret1.N() == test.en {
+			t.Fatalf("test #%v shift() expected %v, but got %v %d", i, test.exp, ret1.runs(), ret1.N())
+		} else if !reflect.DeepEqual(ret2.runs(), test.exp) && c2 == test.carry && ret2.N() == test.en {
+			t.Fatalf("test #%v shiftRun() expected %v, but got %v %d", i, test.exp, ret2.runs(), ret2.N())
 		}
 	}
 }
diff --git a/roaring/roaring_test.go b/roaring/roaring_test.go
index b4f79262..c6ea63eb 100644
--- a/roaring/roaring_test.go
+++ b/roaring/roaring_test.go
@@ -1087,14 +1087,15 @@ func testBitmapQuick(t *testing.T, n int, min, max uint64) {
 		}
 
 		// Remove all values in random order.
-		for _, i := range rand.Perm(len(a)) {
-			removed, _ := bm.Remove(a[i])
+		for i, item := range rand.Perm(len(a)) {
+			removed, _ := bm.Remove(a[item])
 			if removed {
 				manual_count--
 			}
 			//check count
 			if manual_count != bm.Count() {
-				t.Fatalf("expected bitmap Remove count to be: %d got: %d", manual_count, bm.Count())
+				t.Fatalf("removing %d/%d [%d] from bitmap: expected bitmap Remove count to be %d, got %d",
+					i, len(a), a[item], manual_count, bm.Count())
 			}
 		}