Yêu cầu thg 9 16, 1:32 CH 181 0 3
  • 181 0 3
0

Bitset có nhanh hơn mảng bool trong c++ không?

Chia sẻ
  • 181 0 3

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?

3 CÂU TRẢ LỜI


Đã trả lời thg 9 17, 7:28 SA
Đã được chấp nhận
+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:

  1. Xác định chỉ test số lẻ, có thể chỉ tạo mảng số lẻ sẽ tiết kiệm bộ nhớ.
  2. i * i < limit => tính trước sqrt(limit)
  3. 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

Chia sẻ
thg 9 19, 10:23 SA

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

thg 9 19, 10:33 SA

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

Avatar refacore @refacore
thg 9 20, 1:00 SA

@nourist Lý thuyết thì bitset nhanh hơn. Bạn có thể đưa code dùng mảng bool lên để mọi người so sánh.

Đã trả lời thg 9 21, 3:57 SA
+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:

  1. 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...
  2. 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!
  3. 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!

Chia sẻ
thg 9 21, 3:15 CH

Bạn hỏi AI à?

Đã trả lời thg 9 19, 12:12 CH
+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ảng p, 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.
Chia sẻ
thg 9 19, 1:35 CH

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

thg 9 20, 9:25 SA

@nourist vậy bạn có thể post cả code sử dụng mảng bool để so sánh được không?

thg 9 20, 11:10 SA
#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

thg 9 21, 3:27 CH
#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

thg 9 25, 6:47 SA

@nourist

//#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