0
Bitset có nhanh hơn mảng bool trong c++ không?
Mọi người ơi em đang cố gắng để tối ưu sàng nguyên tố eratothenes trong C++ và sau khi tham khảo một số nguồn tin trên google, facebook..v..v.... Thì e biết được là dùng bitset sẽ chiếm ít bộ nhớ và có tốc độ nhanh hơn, em cũng thử code sàng với bitset và thao tác bit thì nó chạy chậm hơn sàng thường sử dụng mảng bool 2 lần.
Code: //code này em bỏ qua sét số chẵn
const int limit = 1e8 + 8;
uint64_t p[limit / 64 + 11];
bool test(int idx) {
return (p[idx / 64] & (1ULL<<(idx % 63))) == 0;
}
void mark(int idx) {
p[idx / 64] |= (1ULL<<(idx % 63));
}
void sieve() {
mark(0);
mark(1);
for (int i = 3; i * i < limit; i += 2) {
if (test(i)) {
for (int j = i * i; j < limit; j += i * 2) {
mark(j);
}
}
}
}
Em muốn hỏi:
- Có phải bitset thật sự nhanh hơn mảng bool không?
- Nếu bitset nhanh hơn mảng bool, vậy tại sao em code thời gian chạy lại lâu hơn?
- Cách fix?
Thêm một bình luận
3 CÂU TRẢ LỜI
+1
Do các hàm test và mark sai địa chỉ, dẫn đến thuật toán chạy liên tục mà không loại bỏ được nhiều phần tử.
1ULL<<(idx % 63) phải là 1ULL<<(idx % 64) (63 sẽ sai với idx = 63)
Một số điểm cần tối ưu:
- Xác định chỉ test số lẻ, có thể chỉ tạo mảng số lẻ sẽ tiết kiệm bộ nhớ.
- i * i < limit => tính trước sqrt(limit)
- Trước hàm mark có thể tối ưu hơn nữa:
// bằng cách này, mình chỉ truy xuất bộ nhớ 1 lần, các tính toán hoàn toàn nằm trong cpu
// cách cũ, mỗi lần gọi hàm mark, cpu đọc lại từ bộ nhớ ô nhớ thứ j / 64
uint64_t marked;
uint64_t j;
for (j = i * i; j < limit; j += i * 2) {
marked |= 1ULL<<(j % 64);
}
p[j / 64] = marked;
PS: phần tối ưu hàm mark chưa đúng và không hiểu quả với i > 31
Phần % 63 là một số sai sót của mình, đáng lẽ phải là 64. Mình sẽ thử lại tối ưu hàm mark
Mình đã thử lại với các góp ý của bạn và thực sự nó không giúp tăng tốc độ. Không biết là bitset có thực sự tăng tốc độ không mình rất thắc mắc, vì tìm kiếm ở đâu cũng thấy là bitset có tốc độ nhanh hơn mảng bool trong khi mình chạy thực tế lại không như vậy
+3
Chào bạn!
Ồ, sàng Eratosthenes, một vấn đề kinh điển của lập trình. Vậy là bạn đã vướng vào "cái bẫy" tối ưu hóa phổ biến.
Về câu hỏi của bạn:
-
Bitset có nhanh hơn mảng bool không?
- Lý thuyết thì đúng rồi, bitset tận dụng khả năng thao tác bit của CPU, nên về mặt lý thuyết nhanh hơn hẳn. Nhưng...
-
Tại sao code của bạn lại chậm hơn?
- Bạn đã mắc phải một lỗi rất phổ biến khi sử dụng bitset trong C++: Truy cập mảng bitset quá nhiều! Mỗi lần truy cập, bạn lại phải tính toán index & bit shift, làm chậm lại quá trình. Trong khi mảng bool, CPU có thể truy cập trực tiếp đến phần tử. Bạn đang "đánh đổi" thời gian truy cập để giảm không gian lưu trữ, mà điều này lại không hiệu quả trong trường hợp này!
-
Cách fix?
- Sử dụng asm: Nếu bạn muốn tối ưu hiệu năng ở cấp độ này thì hãy sử dụng asm. Có thể bạn phải khai báo các biến là register để tối ưu hóa các lệnh ra ngoài, và viết loop theo kiểu asm. Cách này rất khó, nhưng cực kì nhanh.
- Sử dụng vector<bool>: Vector<bool> ở C++ được tối ưu hóa để sử dụng bộ nhớ hiệu quả, nên sẽ tốt hơn mảng bool trong nhiều trường hợp và hiệu năng gần như với bitset, bạn không phải quan tâm tới việc truy cập element.
Lời khuyên:
- Đừng vội vàng tối ưu hóa nếu chưa hiểu rõ code và vấn đề.
- Hãy bắt đầu từ các giải pháp đơn giản trước.
- Cân nhắc kĩ khi sử dụng bitset trong trường hợp này.
Hy vọng câu trả lời của tôi hữu ích với bạn!
Bạn hỏi AI à?
+1
#include <time.h>
const int limit = 1e8 + 8;
long long p[limit / 64 + 11];
bool test(int idx) {
return (p[idx / 64] & (1ULL<<(idx % 63))) == 0;
}
void mark(int idx) {
p[idx / 64] |= (1ULL<<(idx % 63));
}
void sieve() {
mark(0);
mark(1);
for (int i = 3; i * i < limit; i += 2) {
if (test(i)) {
for (long long j = i * i; j < limit; j += i * 2) {
mark(j);
}
}
}
}
#define ri register int
void sieve2() {
ri pSize = limit / 64 + 11;
for(ri i=0; i<pSize; ++i) {
p[i] = 0;
}
register long long* pNum = p;
for (ri i = 3; i < limit; i+=2) {
if (*pNum & (1ULL << (i & 0xff)) == 0) {
for (ri j = i + i; j < limit; j += i) {
p[j >> 8] |= (1ULL<<(j & 0xff));
}
}
if(i & 0xff == 0) {
pNum++;
}
}
}
int main() {
clock_t start = clock();
sieve();
printf("%ld\n", clock() - start);
start = clock();
sieve2();
printf("%ld\n", clock() - start);
getchar();
return 0;
}
- Có thể tối ưu bằng cách sử dụng thanh ghi (register).
- Phép chia cho 64 có thể thay bằng dịch 8 bit sang phải.
- Chia lấy dư cho 64 có thể sử dụng phép và bit với 255 (
& 0xff). - Có thể loại các trường hợp số chia hết cho 2.
- Sử dụng
pNumđể duyệt từng phần tử của mảngp, tránh mỗi lần lại tìm lại phần tử theo chỉ số. - Còn việc tính đến sqrt(limit) thì mình không chắc có đúng không, vì nếu chỉ lấy đến sqrt(limit) thì khai báo limit ngay từ đầu được rồi, cần gì làm limit cho thừa.
hình như hàm sieve2 của bạn bị sai, mình thử in ra bitset của mảng p thì tất cả đều bằng 0. Mình cũng mong bạn giải đáp bitset có thực sự tăng tốc độ không. và nếu tối ưu thì mình mong bạn chỉ tối ưu về phần xử lí bit và không thay đổi những cái khác để mình dễ so sánh
#include <stdio.h>
#include <time.h>
const int limit = 1e8 + 8;
uint64_t p[limit / 64 + 11];
bool test(int idx) {
return (p[idx >> 6] & (1ULL<<(idx & 63))) == 0;
}
void mark(int idx) {
p[idx >> 6] |= (1ULL<<(idx & 63));
}
void sieve() {
mark(0);
mark(1);
for (int i = 3; i * i < limit; i += 2) {
if (test(i)) {
for (int j = i * i; j < limit; j += i * 2) {
mark(j);
}
}
}
}
bool p4[limit + 11] = {false};
bool test4(int idx) {
return p4[idx] == false;
}
void mark4(int idx) {
p4[idx] = true;
}
void sieve4() {
mark4(false);
mark4(true);
for (int i = 3; i * i < limit; i += 2) {
if (test4(i)) {
for (int j = i * i; j < limit; j += i * 2) {
mark4(j);
}
}
}
}
int main() {
const int MAX_TRY = 1;
clock_t start, end;
start = clock();
for(int i=0; i<MAX_TRY; ++i) {
sieve4();
}
end = clock();
printf("sieve bool: %ld ms\n", end - start);
start = clock();
for(int i=0; i<MAX_TRY; ++i) {
sieve();
}
end = clock();
printf("sieve: %ld ms\n", end - start);
return 0;
}
sieve bool: 727587 ms
sieve: 324367 ms
Link test: https://onecompiler.com/cpp/42sr7zes4
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
const int limit = 1e8 + 8;
namespace bitsetSieve {
uint64_t p[limit / 64 + 11];
bool test(int idx) {
return (p[idx / 64] & (1ULL << (idx % 64))) == 0;
}
void mark(int idx) {
p[idx / 64] |= (1ULL << (idx % 64));
}
void sieve() {
mark(0);
mark(1);
for (int i = 3; i * i < limit; i += 2) {
if (test(i)) {
for (int j = i * i; j < limit; j += i * 2) {
mark(j);
}
}
}
}
}
namespace boolSieve {
bool p[limit];
void sieve() {
memset(p, 1, sizeof p);
p[0] = p[1] = 0;
for (int i = 3; i * i < limit; i += 2) {
if (p[i]) {
for (int j = i * i; j < limit; j += i * 2) {
p[j] = 0;
}
}
}
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
clock_t start = clock();
boolSieve::sieve();
cout << "bool sieve: " << clock() - start <<"ms"<< endl;
start = clock();
bitsetSieve::sieve();
cout << "bitset sieve: " << clock() - start <<"ms"<< endl;
return 0;
}
code này so sánh 2 hàm sieve ạ, kết quả:
bool sieve: 1801ms
bitset sieve: 2090ms
//#include <cstdint>
//#include <time.h>
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
const int limit = 1e8 + 8;
namespace bitsetSieve {
uint64_t p[limit / 64 + 11];
bool test(int idx) {
return (p[idx / 64] & (1ULL << (idx % 64))) == 0;
}
void mark(int idx) {
p[idx / 64] |= (1ULL << (idx % 64));
}
void sieve() {
mark(0);
mark(1);
for (int i = 3; i * i < limit; i += 2) {
if (test(i)) {
for (int j = i * i; j < limit; j += i * 2) {
mark(j);
}
}
}
}
}
namespace bitsetSieve2 {
uint32_t p[limit / 32 + 11];
bool test(int idx) {
return (p[idx >> 5] & (1 << (idx % 32)));
}
void mark(int idx) {
p[idx >> 5] &= ~(1 << (idx % 32));
}
void sieve() {
const uint32_t bit1 = ~0;
memset(p, bit1, sizeof p);
p[0] = bit1 - 3;
register uint32_t* pointer = bitsetSieve2::p;
for (int i = 3; i * i < limit; i += 2) {
register int i2 = i % 32;
if(i2 == 1) {
++pointer;
}
if ((*pointer) & (1 << i2)) {
for (int j = i * i; j < limit; j += i * 2) {
p[j >> 5] &= ~(1 << (j % 32));
}
}
}
}
}
namespace boolSieve {
bool p[limit];
void sieve() {
memset(p, 1, sizeof p);
p[0] = p[1] = 0;
for (int i = 3; i * i < limit; i += 2) {
if (p[i]) {
for (int j = i * i; j < limit; j += i * 2) {
p[j] = 0;
}
}
}
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
clock_t start = clock();
boolSieve::sieve();
cout << "bool sieve: " << clock() - start <<"ms"<< endl;
start = clock();
bitsetSieve2::sieve();
cout << "bitset sieve: " << clock() - start <<"ms"<< endl;
for(register int i=0; i<limit; ++i) {
if(boolSieve::p[i] != bitsetSieve2::test(i)) {
cout << i << " - Error! " << endl;
break;
}
}
return 0;
}
Nếu sửa lại để dùng 32bit thì nhanh hơn này
Output:
bool sieve: 1207973ms
bitset sieve: 726665ms
Link test: https://onecompiler.com/cpp/42t7s5m7j
