Flash Memory block write counting & thresholding

Question

I am trying to solve this question:

In a block storage system, new data is written in blocks. We are going to represent the flash memory as one sequential array. We have a list of block writes coming in the form of arrays of size 2: writes[i] = [first_block_written, last_block_written].

Each block has a rewrite limit. If rewrites on a block reach a certain specified threshold we should run a special diagnostic.

Given blockCount (an integer representing the total number of blocks), writes (the list of block-write arrays of size 2), and threshold, your task is to return the list of disjoint block segments, each consisting of blocks that have reached the rewrite threshold. The list of block segments should be sorted in increasing order by their left ends.

Example

For blockCount = 10, writes = [[0, 4], [3, 5], [2, 6]], and threshold = 2, the output should be blockStorageRewrites(blockCount, writes, threshold) = [[2, 5]].

• After the first write, the blocks 0, 1, 2, 3 and 4 were written in once

• After the second write, the blocks 0, 1, 2 and 5 were written in once, and the blocks 3 and 4 reached the rewrite threshold;

• After the final write, the blocks 2 and 5 reached the rewrite threshold as well, so the blocks that should be diagnosed are 2, 3, 4 and 5. Blocks 2, 3, 4 and 5 form one consequent segment [2, 5]. For blockCount = 10, writes = [[0, 4], [3, 5], [2, 6]], and threshold = 3, the output should be blockStorageRewrites(blockCount, writes, threshold) = [[3, 4]];

For blockCount = 10, writes = [[3, 4], [0, 1], [6, 6]], and threshold = 1, the output should be blockStorageRewrites(blockCount, writes, threshold) = [[0, 1], [3, 4], [6, 6]].

I have come up with a correct naive solution here but it's too slow to pass the test cases:

def blockStorageRewrites(blockCount, writes, threshold):
    a = defaultdict(int)
    for (l, r) in writes:
        for i in range(l, r+1):
            a[i] += 1 

    start = None
    res = []
    for i in range(0, blockCount+1):
        if a[i] >=threshold:
            if start is None:
                start = i
        elif a[i] < threshold and start is not None:
            res.append([start, i-1])
            start = None
    return res

How do I optimize it to run faster?

Answer 1

You can get an immediate speed-up by ditching the defaultdict(int), and using a bytearray(blockCount+1) instead. Both have roughly \$O(1)\$ lookup time, but the latter has a much smaller constant factor. In the former, each key must be hashed, then binned, then a linear search through the bin is required to find the correct key entry, if it exists, and creating it if it does not. In the latter, the key is a direct index to the required memory.

This demonstrates a better than 3x improvement of bytearray over defaultdict:

>>> from collections import defaultdict
>>> from timeit import timeit
>>> def original():
    d = defaultdict(int)
    for i in range(1000000):
        d[i] += 1


>>> def using_bytearray():
    b = bytearray(1000000)
    for i in range(1000000):
        b[i] += 1


>>> timeit(original, number=100)
25.083420443999984
>>> timeit(using_bytearray, number=100)
7.779039941000008

Not only is the bytearray faster, it is also more memory efficient. The bytearray uses just 57 bytes of overhead to store an array of 1 million bytes. In contrast, the defaultdict weighs in at over 40x more memory ...

>>> sys.getsizeof(b)
1000057
>>> sys.getsizeof(d)
41943144

... but the real kicker is that is just the size of the dictionary's binning structures. It excludes the size of all of the keys and values stored in the dictionary; those are harder to total as many small integers are interned and don't use additional storage allocation, and duplicate values may point to the same object.

Note: If threshold can exceed 255, you’d need to use array.array instead, with the appropriate type code for the largest rewrite count you’ll experience.

---

Of course, this is still the wrong approach. With writes = [[0, 999999], [1, 1000000]], it should be obvious that block 0 is written once, blocks 1 through 999999 are written twice, and block 1000000 is written once. There is no need to loop through the million indices; we just need to consider the end-points of each range.

So just store the starting & ending points, and the number of times each has been seen. With a sorted array of indices of where the transitions occur, you should be able to iterate over these transition points, and construct your diagnostic list.

Implementation left to student.

Bonus: it is possible use one simple Dict[int,int] structure to store both starting and ending counts, if you think about it the right way.