So sánh mảng nổi với mảng int

Question

Tôi cần một thuật toán tìm kiếm nhị phân được tối ưu hóa trên một dãy số được sắp xếp. Tôi đã làm điều này và thấy rằng việc sử dụng phao đến các số cửa hàng là nhanh hơn so với sử dụng nguyên, bởi vì cuối cùng tôi phải tính toán

(frameNumber-this->frameNumber[imin])/(this->frameNumber[imax]-this->frameNumber[imin]) 

this->frameNumber[imin] là frameNumber lớn nhất ít bình đẳng mà frameNumber và this->frameNumber[imax] là nhỏ nhất lớn hơn bình đẳng hơn cái đó. Mã đó là để tính toán tiến độ giữa hai khung hình chính đó. mảng frameNumber là tĩnh. Tôi chỉ phải sắp xếp nó một lần. Nhưng truy cập nó nhiều lần với tìm kiếm nhị phân và mã trên để tính toán tiến độ.

Chuyển đổi từ int sang float đã dành một số chu kỳ. Sau đó, tôi phát hiện ra rằng trong asm có rất nhiều hướng dẫn fpu. Tôi lo rằng chúng có thể chậm hơn số nguyên.

Vì vậy, đây là câu hỏi. Tôi có thể chuyển đổi một mảng các số dấu chấm động đã sắp xếp thành một int * và chạy tìm kiếm nhị phân trên nó không?

Điều đó có nghĩa:

void binary_search(float key,float* array,...) 
{ 
    int key_integer=*(int*)&key; 
    int* array_intege(int*)array; 
    binary_search_for_integers(key_integer,array_integer,...); 
} 

Hoặc kết luận trên của tôi là sai? (Chẳng hạn như đúc int nổi không phải là quá costy, hoặc so sánh giữa các điểm nổi là như nhau nhanh như số nguyên?

Thanks a lot!

Answer 1

Điều này có vẻ như một ý tưởng tồi. Sử dụng nguyên so sánh trên dữ liệu phao thực sự sẽ cho kết quả trong một mảng ra lệnh một cách chính xác phao, như @rlbond chỉ ra. (Xem http://www.h-schmidt.net/FloatConverter/IEEE754.html để chơi với các cơ quan đại diện nhị phân của phao nổi.) Kiểm tra xem sizeof(int32_t) == sizeof(float) trước khi sử dụng này.

một hack như thế này là không thực sự cần thiết. float so sánh không đắt hơn nhiều so với so sánh int, trên phần cứng hiện đại. (Intel Haswell: ucomiss là 1 uop, với 1 cho mỗi chu kỳ thông qua. So sánh với một toán hạng bộ nhớ là 2 uops, không có vi hợp hạch, mặc dù. Và nó không thể vĩ mô cầu chì như cmp/jcc) Tuy nhiên, FP add/sub và FP mul có độ trễ cao hơn so với các số nguyên tương đương của chúng và ít thông lượng hơn. Dường như ngớ ngẩn để chuyển đổi toàn bộ mảng thành float khi bạn đang viết cho nó chỉ vì bạn muốn thực hiện một số phép toán FP với giá trị tối thiểu và tối đa ở cuối.

Hướng dẫn tải-và-chuyển đổi-int-to-float (x86 cvtsi2ss (số nguyên có dấu 2 số vô hướng)) là nhanh, và lấy không gian mã giống như tải bình thường (movss).

Nếu dữ liệu ban đầu là số nguyên và bạn chỉ sử dụng một số dữ liệu, hãy sử dụng int (tránh chuyển đổi cho các giá trị bạn không bao giờ cần sau này). Nếu bạn truy cập tất cả, và chỉ sử dụng dữ liệu của bạn dưới dạng phao, sau đó lưu nó dưới dạng float. Nếu bạn sử dụng nó như là cả hai, nó có thể là tốt nhất để lưu trữ nó như là int, do đó, nó nhanh hơn khi bạn sử dụng nó như là số nguyên, và về cùng một tốc độ một trong hai cách khi bạn sử dụng nó như là phao.

Từ mẫu mã của bạn, bạn chỉ sử dụng các giá trị ở vị trí tối thiểu và tối đa? Tìm nhanh hơn các giá trị nhỏ nhất và tối đa trong một mảng hơn là sắp xếp toàn bộ mảng. min/max thậm chí còn vector hóa với các lệnh đóng gói-min.

Nhiều nền tảng không có điểm nổi nhanh như CPU ​​Intel hiện đại, vì vậy đừng đi quá mức với điểm nổi.