2
\$\begingroup\$

This is partially inspired by this question

I have started creating an example to show how to keep certain parts of the array on disk and came up with the following:

#include <fstream>
#include <iostream>
#include <vector>

#ifdef _WIN32
std::string createTempFileName()
{
    char buf[800];
    tmpnam_s(buf, sizeof(buf));
    return buf;
}
#else
std::string createTempFileName()
{
    char filename[] = "/tmp/mytemp.XXXXXX"; // template for our file.        
    int fd = mkstemp(filename);
    return filename;
}
#endif

template <class T, std::size_t blockSize>
class Block
{
public:
    explicit Block(std::size_t blockIndex)
    {
        inRAM = true;
        index = blockIndex;
        offset = 0;
        data.resize(blockSize);
        used = 0;
    }

    void write(std::fstream& file)
    {
        file.seekg(offset, std::ios::beg);
        file.write((char*)data.data(), sizeof(T) * blockSize);
        data.resize(0);
        inRAM = false;
    }

    void read(std::fstream& file)
    {
        file.seekg(offset, std::ios::beg);
        data.resize(blockSize);
        file.read((char*)data.data(), sizeof(T) * blockSize);
        inRAM = true;
    }

public:
    bool inRAM;
    std::size_t used;
    std::size_t index;
    std::size_t offset;
    std::vector<T> data;
};

template <class T, std::size_t blockSize, std::size_t maxBlocksInRAM>
class BigList
{
public:
    BigList()
    {
        offset = 0;
        temp.open(createTempFileName(), std::ios_base::out | std::ios_base::in | std::ios_base::trunc | std::ios_base::binary);
        blocks.emplace_back(blocks.size());
        blocksInRAM.push_back(blocks.back().index);
    }

    void add(const T value)
    {
        // check if block is in memory and have space available
        if (blocks.back().inRAM == false && blocks.back().used < blockSize)
        {
            flushBlockIfNeeded();
            blocks.back().read(temp);
            blocksInRAM.push_back(blocks.back().index);
        }
        // check if block have space available
        if (blocks.back().used == blockSize)
        {
            flushBlockIfNeeded();
            blocks.emplace_back(blocks.size());
            blocksInRAM.push_back(blocks.back().index);
        }
        // add value to block
        blocks.back().data[blocks.back().used++] = value;
    }

    const T& get(std::uint64_t index)
    {
        std::size_t blockIndex = index / blockSize;
        std::size_t itemIndex = index % blockSize;
        auto& block = blocks.at(blockIndex);
        if (block.inRAM == false)
        {
            flushBlockIfNeeded();
            block.read(temp);
            blocksInRAM.push_back(blockIndex);
        }
        return block.data.at(itemIndex);
    }

private:
    void flushBlockIfNeeded()
    {
        if (blocksInRAM.size() == maxBlocksInRAM)
        {
            auto& block = blocks[blocksInRAM[0]];
            if (block.offset == 0)
            {
                block.offset = offset;
                offset += sizeof(T) * blockSize;
            }
            block.write(temp);
            blocksInRAM.erase(blocksInRAM.begin());
        }
    }

    std::size_t offset;
    std::vector<Block<T, blockSize>> blocks;
    std::vector<std::size_t> blocksInRAM;
    std::fstream temp;
};

int main()
{
    BigList<int, 16, 4> list;
    for (int i = 0; i < 254; i++)
        list.add(i * 10);

    for (int i = 0; i < 128; i++)
        std::cout << list.get(i) << '\n';

    list.add(2550);
    list.add(2560);

    for (int i = 0; i < 256; i++)
        std::cout << list.get(i) << '\n';
}
\$\endgroup\$
4
  • \$\begingroup\$ Why not use MapViewOfFile ? \$\endgroup\$
    – JDługosz
    Nov 8 at 20:35
  • \$\begingroup\$ @JDługosz, isn't MapViewOfFile a Win32-specific thing? I wanted to create something that is at least partially portable. \$\endgroup\$
    – jdt
    Nov 8 at 20:41
  • \$\begingroup\$ Yes, for Posix use mmap. I saw you had Win32-specific code so just used that name. \$\endgroup\$
    – JDługosz
    Nov 8 at 20:43
  • \$\begingroup\$ @JDługosz, thanks, it looks interesting. \$\endgroup\$
    – jdt
    Nov 8 at 21:38
4
\$\begingroup\$

Safely creating a temporary file

Creating a temporary file safely is harder than you think. The way you do it is unfortunately not safe. For the Linux version, you are ignoring the return value of mkstemp(), this leaks the filedescriptor. Another process might replace the temporary file you just created with mkstemp() with a symlink to another file before your process gets around to opening the std::fstream. It's even more unfortunate that there is no safe way to do this in standard C++.

Of course this does not affect class BigList itself.

Make maxBlocksInRAM a regular member variable

There is little reason to make maxBlocksInRAM a template parameter. It is not improving type safety, nor making the code more efficient.

Provide defaults for blockSize and maxBlocksInRAM

As a user of a BigList, I don't want to worry about how to efficiently load and save blocks. Ideally, it just should use the optimal block size and the number of resident blocks automatically. A simple way to do this is to provide default values for these (template) parameters:

template <class T, std::size_t blockSize = 1024>
class BigList {
    ...
};

Think about lifetimes of references

The member function get() returns a reference to a T. However, you don't know how long the caller of get() is going to keep this reference around. Ideally, you want to ensure that the Block it came from stays in RAM for however long the reference is still used. One way to do this is to return something similar to a std::shared_ptr. You can add a reference counter to Block, and have get() return a RAII object that increases the refcount of the owning Block in its constructor, and decreases it in its destructor. Also, the logic of flushBlockIfNeeded() should be changed to never flush a block that has a non-zero reference count.

Consider the overhead of a Block

You only ever add Blocks to the vector blocks, you never remove them. A Block that has inRAM == false is still using some memory. On my machine, it is using 56 bytes of memory per Block. If you only store 16 ints per Block, that is a lot of overhead.

You can of course easily increase blockSize and reduce the overhead, but it is still non-zero, and grows the more Blocks there are in the BigList. Instead of keeping empty Blocks around, consider removing them entirely. A possible way is to avoid having both blocks and blocksInRAM, and just have a std::set<Block> blocks, and overload Block::operator<() so the Blocks are ordered by their index. Then in get() you do:

std::size_t blockIndex = index / blockSize;
auto it = blocks.find(blockIndex);
if (it == blocks.end()) {
    // It's not in RAM, read it in
} else {
    // It's in RAM
    auto &block = *it;
    ...
}

If course, this is more expensive. There are better data structures than std::set, but they are not in the STL.

\$\endgroup\$
1
\$\begingroup\$

So this is meant to get and store single values of type T. It doesn't return a durable pointer that you can use for the block of values for a while after fetching it, right?

So what does this do that the normal disk caching doesn't handle? You're not doing anything to turn off the normal caching from ostreams or the operating system. So, you're just re-copying values that are still in memory anyway.

That is, when you call get, your code first looks in your list of loaded blocks. If it's not present, it reads from the fstream which probably buffers a single region only, so it will be found for the same or neighboring block; that's probably a waste of memory and overhead since it will only hold things that are already in your loaded blocks. Then it calls the file system in the OS, which will remember individual sectors (or 64K groups of consecutive sectors) of the file, pretty much in the identical way that your code is implementing. Being a MRU system, it probably holds the same stuff that you are!

\$\endgroup\$
6
  • \$\begingroup\$ The point of this is creating a list that would not fit in the address space. Consider running this example in 32-bit mode. \$\endgroup\$
    – jdt
    Nov 9 at 15:42
  • \$\begingroup\$ @upkajdt yes, but reading the desired value from the file in the get function, without adding your own layer of cacheing, should work just as well. Try it and see if there's a performance difference. \$\endgroup\$
    – JDługosz
    Nov 9 at 15:45
  • \$\begingroup\$ Using the following test it appears that running on Windows 10, using BigList is at least 10 x faster than simply writing the data to a file. \$\endgroup\$
    – jdt
    Nov 9 at 16:13
  • \$\begingroup\$ Here I have modified the benchmark to only measure the reading time. \$\endgroup\$
    – jdt
    Nov 9 at 16:41
  • \$\begingroup\$ @upkajdt So, you are saving the overhead of the system call for the read. Skip the fstream and use Windows API directly, and specify flags for no buffering, and set your blocksize to a multiple of 64K and read aligned blocks from the file (that will let you completely eliminate the buffering inside the OS, and do DMA direct to your buffer). \$\endgroup\$
    – JDługosz
    Nov 9 at 16:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.