Binary search

• Deadline: 2026/05/11 23:59
• Test wrapper + empty implementation shared with other assignments
• Points:
  • 120 pts for solution working at nominal speed (i.e. as fast as an unpublished reference solution)
  • +/-80 pts per ten-fold speed-up/slow-down, logarithmically

The input consists of an ordered sequence idata with isize elements and an unordered sequence odata with osize elements. The assignment is to distribute the odata into (isize+1) buckets, whose border values are defined by idata. In the bucket number k, elements are greater or equal to idata[k-1] and less than idata[k].

• The class bsearch_inner is intended to hold a searching structure, containing data copied from idata.
• The time used to create the structure is not measured.

        typedef std::int32_t data_element;
        
        template< typename policy>
        class bsearch_inner {
        public:
            bsearch_inner( const data_element * idata, std::size_t isize);
        };
    

• The class bsearch_outer serves as a buffer for the storage of intermediate and final results.
• The constructor allocates the necessary space.
• A call to bucketize(odata) performs the distribution to buckets as described above. This is the function whose run-time is measured.
• After calling bucketize, a call to bucket(k) returns a reference to the data of the bucket number k. bucket shall return in constant time.
• Repeated calls to bucketize overwrite the previous results; any references returned from the preceding calls to bucket(k) are no longer valid.
• All calls to bucketize(odata) use the same number of elements (osize), specified previously in the constructor call.
• The interface is designed to avoid allocation in bucketize or bucket.
• In the testing envelope, each thread uses its own instance of bsearch_outer; all these instances are linked to the same instance of bsearch_inner.

        template< typename policy>
        class bsearch_outer { 
        public:
            bsearch_outer( const bsearch_inner< policy> & inner, std::size_t osize);
    
            void bucketize( const data_element * odata);
            
            typedef std::pair< const data_element *, std::size_t> bucket_rv;
    
            bucket_rv bucket( std::size_t k) const;
        };
    

For relevant performance measurement at parlab, the program shall be run as:

            srun -p mpi-homo-short -n 1 -c 64 <build-folder>/bsearch --direct-print=no --threads=32
        

Test parameters

isize and osize parameters are explained above. isize is iterated through the set { 64, 256, 1024, 4096, 16384, 65536, 262144, 1048576 }, osize through the set { 1024, 16384, 262144 }, resulting in 24 test configurations on each platform. In Debug mode, only 6 of them are used.

repeats is an auto-adjusted parameter, used to increase running time by repeatedly calling compute. The range of the parameter is set so that the expected run time ranges from fractions of a second to seconds (stopped by the auto-adjustment mechanism after exceeding a second).