std::bitset by Vegan Fanatic

Well post the fixed <bitset> on Windows update for Visual Studio users. Then those of us who are math oriented can take advantage of gigantic fields of bits when exploring various topics.

My example sieve was simply an example of one possible use. Sieve could potentially be used with trillions of bits given enough RAM on a machine.

I like the idea under a 64-bit build of supporting 18 exabits.

Hi,

Thanks again for reporting this issue. I've squashed the spurious warning for gigantic bitsets, and replaced bitset's use of int with ptrdiff_t, so I'm resolving this as Fixed (although as I previously demonstrated, 8 gigabit bitsets already worked properly).

As always, if you have any further questions, feel free to E-mail me at stl@microsoft.com .

Stephan T. Lavavej
Visual C++ Libraries Developer

I was expecting std::bitset would use size_t for the index and it would use size_t as the base object with code to do the bit shift as needed to access the individual bit in question.

I use size_t as my pointer type all the time with classes and templates. This type is supposed to be the largest pointer possible for a given machine, but some do not respect the standard such as the old Cray Y-MP machines.

For that reason I have to use sizeof(size_t) to make sure I do not screw up.

I believe in the code I supplied I used size_t but I may have use int out of haste to make an example.

Generally I use size_t for counters and pointers as its the only 64-bit object outside using an intrinsic.

Unrelated, the email I recieved notifying me of your post did not show the entire code as I see here. The #includes were not shown.

bitset does use int when it should use size_t or ptrdiff_t. This appears to be a theoretical concern that affects only bitsets of 128 gigabits (16 gigabytes) or larger. (That's because large bitsets use 64-bit chunks, and due to the ints, bitset can address up to 2^31 - 1 chunks, so 2^37 bits is the limit.) 8 gigabits (1 gigabyte) works just fine:

C:\Temp>type meow.cpp
#include <stddef.h>
#include <bitset>
#include <iostream>
#include <memory>
#include <ostream>
using namespace std;

const size_t N = 8589934592;

int main() {
    auto sp = make_shared<bitset<N>>();

    sp->flip();

    const bool prime = true;
    const bool composite = false;

    for (size_t i = 2; i * i < N; ++i) {
        if ((*sp)[i] == prime) {
            for (size_t k = i * 2; k < N; k += i) {
                (*sp)[k] = composite;
            }
        }
    }

    const size_t K = 10;

    cout << "The " << K << " largest primes below " << N << " are:" << endl;

    for (size_t i = 0, k = 0; i < N && k < K; ++i) {
        if ((*sp)[N - 1 - i] == prime) {
            cout << N - 1 - i << endl;
            ++k;
        }
    }

    cout << "Done!" << endl;
}

C:\Temp>cl
Microsoft (R) C/C++ Optimizing Compiler Version 16.00.30319.01 for x64
Copyright (C) Microsoft Corporation. All rights reserved.

usage: cl [ option... ] filename... [ /link linkoption... ]

C:\Temp>cl /EHsc /nologo /W4 /MT /O2 /GL meow.cpp
meow.cpp
C:\Program Files (x86)\Microsoft Visual Studio 10.0\VC\INCLUDE\bitset(39) : warning C4341: '_EEN_BITS' : signed value is out of range for enum constant
        meow.cpp(13) : see reference to class template instantiation 'std::bitset<_Bits>' being compiled
        with
        [
            _Bits=0x20
        ]
C:\Program Files (x86)\Microsoft Visual Studio 10.0\VC\INCLUDE\bitset(39) : warning C4309: 'initializing' : truncation of constant value
Generating code
Finished generating code

C:\Temp>meow
The 10 largest primes below 8589934592 are:
8589934583
8589934567
8589934543
8589934513
8589934487
8589934307
8589934291
8589934289
8589934271
8589934237
Done!

Note that I use shared_ptr because I can't put a gigabyte bitset on the stack (when I tried, I triggered a stack overflow). Also note that I'm not using "#pragma omp parallel for" as multithreading is irrelevant here (it's possible that you were having multiple threads simultaneously modifying the same chunk, which is incorrect).

While 128 gigabits is ridiculously enormous, and I don't even have 16 gigabytes of virtual memory, I'll look into fixing that issue. I'll also see about fixing that spurious _EEN_BITS warning.

Stephan T. Lavavej
Visual C++ Libraries Developer

seive1.cpp will reproduce the problem. I made this especially for highlighting the imperfection in the std::bitset which is not using size_t for the pointer.

Given adequate RAM, why not use a 32 gigabit database. The sieve revealed that thinking as wishful.

Hi,

Thanks for reporting this issue. However, I'm unsure as to whether you're reporting a problem with bitset (as the Title says) or with vector<bool> (as the Repro Steps say) or with both.

What I require is a self-contained test case that I can copy and paste into a text file so that I can observe the error. It must trigger the error with no alterations; of course, you can include comments describing what happens if you alter various constants and so forth. What I want to avoid is confusion caused by programs of the form "this works, but tweak X, Y, and Z, and it fails".

I'll compile your test case, for x64 as you specified, from the command line with "cl /EHsc /nologo /W4 /MTd program.cpp" unless you tell me otherwise. Additionally, please describe the exact error that you're observing; I see references to "the error" but not its nature - is it a crash, a hang, a debug assertion, or something else?

I also don't know what "I have also noted that the std::bitset is not bit stable when copying to another object." refers to. Again, I'll need a self-contained test case for that.

Because we cannot leave bugs open forever, if I don't hear back from you within 7 days, I'll have to close this issue as Not Reproducible.

If you have any further questions, feel free to E-mail me at stl@microsoft.com .

Stephan T. Lavavej
Visual C++ Libraries Developer

I suggest that increasing the size of p in the sieve will show the problem. When building for AMD64 it remains a 32-bit sized object so somebody forgot to use size_t as the container pointer.

I am currently standing by for an update from you and would like to know how things are going on your end. If you could get back to me at your earliest convenience with information I request, we will be able to make headway towards a resolution. I look forward to hearing from you.

Thanks for reporting this issue. In order to fix the issue, we must first reproduce the issue in our labs. We are unable to reproduce the issue with the steps you provided.

Please give us a demo project to demonstrate this issue so that we can conduct further research.

It would be greatly appreciated if you could provide us with that information as quickly as possible. If we do not hear back from you within 7 days, we will close this issue.

Thanks again for your efforts and we look forward to hearing from you.

Microsoft Visual Studio Connect Support Team

Thank you for your feedback, we are currently reviewing the issue you have submitted. If this issue is urgent, please contact support directly(http://support.microsoft.com)