1 // -*- mode:C++; tab-width:8; c-basic-offset:2; indent-tabs-mode:t -*-
2 // vim: ts=8 sw=2 smarttab
8 #include <boost/lexical_cast.hpp>
9 #include <boost/icl/interval_map.hpp>
10 #include <boost/algorithm/string/join.hpp>
12 #include "common/SubProcess.h"
13 #include "common/fork_function.h"
15 #include "include/stringify.h"
16 #include "CrushTester.h"
17 #include "CrushTreeDumper.h"
18 #include "common/ceph_context.h"
19 #include "include/ceph_features.h"
20 #include "common/debug.h"
22 #define dout_subsys ceph_subsys_crush
24 #define dout_prefix *_dout << "CrushTester: "
29 using std::ostringstream
;
31 using std::stringstream
;
34 void CrushTester::set_device_weight(int dev
, float f
)
36 int w
= (int)(f
* 0x10000);
41 device_weight
[dev
] = w
;
44 int CrushTester::get_maximum_affected_by_rule(int ruleno
)
46 // get the number of steps in RULENO
47 int rule_size
= crush
.get_rule_len(ruleno
);
48 vector
<int> affected_types
;
49 map
<int,int> replications_by_type
;
51 for (int i
= 0; i
< rule_size
; i
++){
52 // get what operation is done by the current step
53 int rule_operation
= crush
.get_rule_op(ruleno
, i
);
55 // if the operation specifies choosing a device type, store it
56 if (rule_operation
>= 2 && rule_operation
!= 4){
57 int desired_replication
= crush
.get_rule_arg1(ruleno
,i
);
58 int affected_type
= crush
.get_rule_arg2(ruleno
,i
);
59 affected_types
.push_back(affected_type
);
60 replications_by_type
[affected_type
] = desired_replication
;
65 * now for each of the affected bucket types, see what is the
66 * maximum we are (a) requesting or (b) have
69 map
<int,int> max_devices_of_type
;
71 // loop through the vector of affected types
72 for (vector
<int>::iterator it
= affected_types
.begin(); it
!= affected_types
.end(); ++it
){
73 // loop through the number of buckets looking for affected types
74 for (map
<int,string
>::iterator p
= crush
.name_map
.begin(); p
!= crush
.name_map
.end(); ++p
){
75 int bucket_type
= crush
.get_bucket_type(p
->first
);
76 if ( bucket_type
== *it
)
77 max_devices_of_type
[*it
]++;
81 for(std::vector
<int>::iterator it
= affected_types
.begin(); it
!= affected_types
.end(); ++it
){
82 if ( replications_by_type
[*it
] > 0 && replications_by_type
[*it
] < max_devices_of_type
[*it
] )
83 max_devices_of_type
[*it
] = replications_by_type
[*it
];
87 * get the smallest number of buckets available of any type as this is our upper bound on
88 * the number of replicas we can place
90 int max_affected
= std::max( crush
.get_max_buckets(), crush
.get_max_devices() );
92 for(std::vector
<int>::iterator it
= affected_types
.begin(); it
!= affected_types
.end(); ++it
){
93 if (max_devices_of_type
[*it
] > 0 && max_devices_of_type
[*it
] < max_affected
)
94 max_affected
= max_devices_of_type
[*it
];
101 map
<int,int> CrushTester::get_collapsed_mapping()
103 int num_to_check
= crush
.get_max_devices();
105 map
<int, int> collapse_mask
;
107 for (int i
= 0; i
< num_to_check
; i
++){
108 if (crush
.check_item_present(i
)){
109 collapse_mask
[i
] = next_id
;
114 return collapse_mask
;
117 void CrushTester::adjust_weights(vector
<__u32
>& weight
)
120 if (mark_down_device_ratio
> 0) {
122 vector
<int> bucket_ids
;
123 for (int i
= 0; i
< crush
.get_max_buckets(); i
++) {
125 if (crush
.get_bucket_weight(id
) > 0) {
126 bucket_ids
.push_back(id
);
130 // get buckets that are one level above a device
131 vector
<int> buckets_above_devices
;
132 for (unsigned i
= 0; i
< bucket_ids
.size(); i
++) {
133 // grab the first child object of a bucket and check if it's ID is less than 0
134 int id
= bucket_ids
[i
];
135 if (crush
.get_bucket_size(id
) == 0)
137 int first_child
= crush
.get_bucket_item(id
, 0); // returns the ID of the bucket or device
138 if (first_child
>= 0) {
139 buckets_above_devices
.push_back(id
);
143 // permute bucket list
144 for (unsigned i
= 0; i
< buckets_above_devices
.size(); i
++) {
145 unsigned j
= lrand48() % (buckets_above_devices
.size() - 1);
146 std::swap(buckets_above_devices
[i
], buckets_above_devices
[j
]);
149 // calculate how many buckets and devices we need to reap...
150 int num_buckets_to_visit
= (int) (mark_down_bucket_ratio
* buckets_above_devices
.size());
152 for (int i
= 0; i
< num_buckets_to_visit
; i
++) {
153 int id
= buckets_above_devices
[i
];
154 int size
= crush
.get_bucket_size(id
);
156 for (int o
= 0; o
< size
; o
++)
157 items
.push_back(crush
.get_bucket_item(id
, o
));
160 for (int o
= 0; o
< size
; o
++) {
161 int j
= lrand48() % (crush
.get_bucket_size(id
) - 1);
162 std::swap(items
[o
], items
[j
]);
165 int local_devices_to_visit
= (int) (mark_down_device_ratio
*size
);
166 for (int o
= 0; o
< local_devices_to_visit
; o
++){
167 int item
= crush
.get_bucket_item(id
, o
);
174 bool CrushTester::check_valid_placement(int ruleno
, vector
<int> in
, const vector
<__u32
>& weight
)
177 bool valid_placement
= true;
178 vector
<int> included_devices
;
179 map
<string
,string
> seen_devices
;
181 // first do the easy check that all devices are "up"
182 for (vector
<int>::iterator it
= in
.begin(); it
!= in
.end(); ++it
) {
183 if (weight
[(*it
)] == 0) {
184 valid_placement
= false;
186 } else if (weight
[(*it
)] > 0) {
187 included_devices
.push_back( (*it
) );
192 * now do the harder test of checking that the CRUSH rule r is not violated
193 * we could test that none of the devices mentioned in out are unique,
194 * but this is a special case of this test
197 // get the number of steps in RULENO
198 int rule_size
= crush
.get_rule_len(ruleno
);
199 vector
<string
> affected_types
;
201 // get the smallest type id, and name
202 int min_map_type
= crush
.get_num_type_names();
203 for (map
<int,string
>::iterator it
= crush
.type_map
.begin(); it
!= crush
.type_map
.end(); ++it
) {
204 if ( (*it
).first
< min_map_type
) {
205 min_map_type
= (*it
).first
;
209 string min_map_type_name
= crush
.type_map
[min_map_type
];
211 // get the types of devices affected by RULENO
212 for (int i
= 0; i
< rule_size
; i
++) {
213 // get what operation is done by the current step
214 int rule_operation
= crush
.get_rule_op(ruleno
, i
);
216 // if the operation specifies choosing a device type, store it
217 if (rule_operation
>= 2 && rule_operation
!= 4) {
218 int affected_type
= crush
.get_rule_arg2(ruleno
,i
);
219 affected_types
.push_back( crush
.get_type_name(affected_type
));
223 // find in if we are only dealing with osd's
224 bool only_osd_affected
= false;
225 if (affected_types
.size() == 1) {
226 if ((affected_types
.back() == min_map_type_name
) && (min_map_type_name
== "osd")) {
227 only_osd_affected
= true;
231 // check that we don't have any duplicate id's
232 for (vector
<int>::iterator it
= included_devices
.begin(); it
!= included_devices
.end(); ++it
) {
233 int num_copies
= std::count(included_devices
.begin(), included_devices
.end(), (*it
) );
234 if (num_copies
> 1) {
235 valid_placement
= false;
239 // if we have more than just osd's affected we need to do a lot more work
240 if (!only_osd_affected
) {
241 // loop through the devices that are "in/up"
242 for (vector
<int>::iterator it
= included_devices
.begin(); it
!= included_devices
.end(); ++it
) {
243 if (valid_placement
== false)
246 // create a temporary map of the form (device type, device name in map)
247 map
<string
,string
> device_location_hierarchy
= crush
.get_full_location(*it
);
249 // loop over the types affected by RULENO looking for duplicate bucket assignments
250 for (vector
<string
>::iterator t
= affected_types
.begin(); t
!= affected_types
.end(); ++t
) {
251 if (seen_devices
.count( device_location_hierarchy
[*t
])) {
252 valid_placement
= false;
255 // store the devices we have seen in the form of (device name, device type)
256 seen_devices
[ device_location_hierarchy
[*t
] ] = *t
;
262 return valid_placement
;
265 int CrushTester::random_placement(int ruleno
, vector
<int>& out
, int maxout
, vector
<__u32
>& weight
)
267 // get the total weight of the system
268 int total_weight
= 0;
269 for (unsigned i
= 0; i
< weight
.size(); i
++)
270 total_weight
+= weight
[i
];
272 if (total_weight
== 0 ||
273 crush
.get_max_devices() == 0)
276 // determine the real maximum number of devices to return
277 int devices_requested
= std::min(maxout
, get_maximum_affected_by_rule(ruleno
));
278 bool accept_placement
= false;
280 vector
<int> trial_placement(devices_requested
);
281 int attempted_tries
= 0;
284 // create a vector to hold our trial mappings
285 int temp_array
[devices_requested
];
286 for (int i
= 0; i
< devices_requested
; i
++){
287 temp_array
[i
] = lrand48() % (crush
.get_max_devices());
290 trial_placement
.assign(temp_array
, temp_array
+ devices_requested
);
291 accept_placement
= check_valid_placement(ruleno
, trial_placement
, weight
);
293 } while (accept_placement
== false && attempted_tries
< max_tries
);
295 // save our random placement to the out vector
296 if (accept_placement
)
297 out
.assign(trial_placement
.begin(), trial_placement
.end());
300 else if (attempted_tries
== max_tries
)
306 void CrushTester::write_integer_indexed_vector_data_string(vector
<string
> &dst
, int index
, vector
<int> vector_data
)
308 stringstream
data_buffer (stringstream::in
| stringstream::out
);
309 unsigned input_size
= vector_data
.size();
311 // pass the indexing variable to the data buffer
312 data_buffer
<< index
;
314 // pass the rest of the input data to the buffer
315 for (unsigned i
= 0; i
< input_size
; i
++) {
316 data_buffer
<< ',' << vector_data
[i
];
319 data_buffer
<< std::endl
;
321 // write the data buffer to the destination
322 dst
.push_back( data_buffer
.str() );
325 void CrushTester::write_integer_indexed_vector_data_string(vector
<string
> &dst
, int index
, vector
<float> vector_data
)
327 stringstream
data_buffer (stringstream::in
| stringstream::out
);
328 unsigned input_size
= vector_data
.size();
330 // pass the indexing variable to the data buffer
331 data_buffer
<< index
;
333 // pass the rest of the input data to the buffer
334 for (unsigned i
= 0; i
< input_size
; i
++) {
335 data_buffer
<< ',' << vector_data
[i
];
338 data_buffer
<< std::endl
;
340 // write the data buffer to the destination
341 dst
.push_back( data_buffer
.str() );
344 void CrushTester::write_integer_indexed_scalar_data_string(vector
<string
> &dst
, int index
, int scalar_data
)
346 stringstream
data_buffer (stringstream::in
| stringstream::out
);
348 // pass the indexing variable to the data buffer
349 data_buffer
<< index
;
351 // pass the input data to the buffer
352 data_buffer
<< ',' << scalar_data
;
353 data_buffer
<< std::endl
;
355 // write the data buffer to the destination
356 dst
.push_back( data_buffer
.str() );
358 void CrushTester::write_integer_indexed_scalar_data_string(vector
<string
> &dst
, int index
, float scalar_data
)
360 stringstream
data_buffer (stringstream::in
| stringstream::out
);
362 // pass the indexing variable to the data buffer
363 data_buffer
<< index
;
365 // pass the input data to the buffer
366 data_buffer
<< ',' << scalar_data
;
367 data_buffer
<< std::endl
;
369 // write the data buffer to the destination
370 dst
.push_back( data_buffer
.str() );
373 int CrushTester::test_with_fork(CephContext
* cct
, int timeout
)
375 ldout(cct
, 20) << __func__
<< dendl
;
377 int r
= fork_function(timeout
, sink
, [&]() {
380 if (r
== -ETIMEDOUT
) {
381 err
<< "timed out during smoke test (" << timeout
<< " seconds)";
387 class BadCrushMap
: public std::runtime_error
{
390 BadCrushMap(const char* msg
, int id
)
391 : std::runtime_error(msg
), item(id
) {}
393 // throws if any node in the crush fail to print
394 class CrushWalker
: public CrushTreeDumper::Dumper
<void> {
395 typedef void DumbFormatter
;
396 typedef CrushTreeDumper::Dumper
<DumbFormatter
> Parent
;
399 CrushWalker(const CrushWrapper
*crush
, unsigned max_id
)
400 : Parent(crush
, CrushTreeDumper::name_map_t()), max_id(max_id
) {}
401 void dump_item(const CrushTreeDumper::Item
&qi
, DumbFormatter
*) override
{
403 if (qi
.is_bucket()) {
404 if (!crush
->get_item_name(qi
.id
)) {
405 throw BadCrushMap("unknown item name", qi
.id
);
407 type
= crush
->get_bucket_type(qi
.id
);
409 if (max_id
> 0 && qi
.id
>= max_id
) {
410 throw BadCrushMap("item id too large", qi
.id
);
414 if (!crush
->get_type_name(type
)) {
415 throw BadCrushMap("unknown type name", qi
.id
);
421 bool CrushTester::check_name_maps(unsigned max_id
) const
423 CrushWalker
crush_walker(&crush
, max_id
);
425 // walk through the crush, to see if its self-contained
426 crush_walker
.dump(NULL
);
427 // and see if the maps is also able to handle straying OSDs, whose id >= 0.
428 // "ceph osd tree" will try to print them, even they are not listed in the
430 crush_walker
.dump_item(CrushTreeDumper::Item(0, 0, 0, 0), NULL
);
431 } catch (const BadCrushMap
& e
) {
432 err
<< e
.what() << ": item#" << e
.item
<< std::endl
;
438 int CrushTester::test(CephContext
* cct
)
440 ldout(cct
, 20) << dendl
;
441 if (min_rule
< 0 || max_rule
< 0) {
443 max_rule
= crush
.get_max_rules() - 1;
445 if (min_x
< 0 || max_x
< 0) {
449 if (min_rep
< 0 && max_rep
< 0) {
450 cerr
<< "must specify --num-rep or both --min-rep and --max-rep" << std::endl
;
454 // initial osd weights
455 vector
<__u32
> weight
;
458 * note device weight is set by crushtool
459 * (likely due to a given a command line option)
461 for (int o
= 0; o
< crush
.get_max_devices(); o
++) {
462 if (device_weight
.count(o
)) {
463 weight
.push_back(device_weight
[o
]);
464 } else if (crush
.check_item_present(o
)) {
465 weight
.push_back(0x10000);
471 if (output_utilization_all
)
472 cerr
<< "devices weights (hex): " << std::hex
<< weight
<< std::dec
<< std::endl
;
475 adjust_weights(weight
);
478 int num_devices_active
= 0;
479 for (vector
<__u32
>::iterator p
= weight
.begin(); p
!= weight
.end(); ++p
)
481 num_devices_active
++;
483 if (output_choose_tries
)
484 crush
.start_choose_profile();
486 for (int r
= min_rule
; r
< crush
.get_max_rules() && r
<= max_rule
; r
++) {
487 ldout(cct
, 20) << "rule: " << r
<< dendl
;
489 if (!crush
.rule_exists(r
)) {
490 if (output_statistics
)
491 err
<< "rule " << r
<< " dne" << std::endl
;
495 if (output_statistics
)
496 err
<< "rule " << r
<< " (" << crush
.get_rule_name(r
)
497 << "), x = " << min_x
<< ".." << max_x
498 << ", numrep = " << min_rep
<< ".." << max_rep
501 for (int nr
= min_rep
; nr
<= max_rep
; nr
++) {
502 ldout(cct
, 20) << "current numrep: " << nr
<< dendl
;
504 vector
<int> per(crush
.get_max_devices());
507 int num_objects
= ((max_x
- min_x
) + 1);
508 float num_devices
= (float) per
.size(); // get the total number of devices, better to cast as a float here
510 // create a structure to hold data for post-processing
511 tester_data_set tester_data
;
512 vector
<float> vector_data_buffer_f
;
514 // create a map to hold batch-level placement information
515 map
<int, vector
<int> > batch_per
;
516 int objects_per_batch
= num_objects
/ num_batches
;
517 int batch_min
= min_x
;
518 int batch_max
= min_x
+ objects_per_batch
- 1;
520 // get the total weight of the system
521 int total_weight
= 0;
522 for (unsigned i
= 0; i
< per
.size(); i
++)
523 total_weight
+= weight
[i
];
525 if (total_weight
== 0)
528 // compute the expected number of objects stored per device in the absence of weighting
529 float expected_objects
= std::min(nr
, get_maximum_affected_by_rule(r
)) * num_objects
;
531 // compute each device's proportional weight
532 vector
<float> proportional_weights( per
.size() );
534 for (unsigned i
= 0; i
< per
.size(); i
++)
535 proportional_weights
[i
] = (float) weight
[i
] / (float) total_weight
;
537 if (output_data_file
) {
538 // stage the absolute weight information for post-processing
539 for (unsigned i
= 0; i
< per
.size(); i
++) {
540 tester_data
.absolute_weights
[i
] = (float) weight
[i
] / (float)0x10000;
543 // stage the proportional weight information for post-processing
544 for (unsigned i
= 0; i
< per
.size(); i
++) {
545 if (proportional_weights
[i
] > 0 )
546 tester_data
.proportional_weights
[i
] = proportional_weights
[i
];
548 tester_data
.proportional_weights_all
[i
] = proportional_weights
[i
];
552 // compute the expected number of objects stored per device when a device's weight is considered
553 vector
<float> num_objects_expected(num_devices
);
555 for (unsigned i
= 0; i
< num_devices
; i
++)
556 num_objects_expected
[i
] = (proportional_weights
[i
]*expected_objects
);
558 for (int current_batch
= 0; current_batch
< num_batches
; current_batch
++) {
559 if (current_batch
== (num_batches
- 1)) {
561 objects_per_batch
= (batch_max
- batch_min
+ 1);
564 float batch_expected_objects
= std::min(nr
, get_maximum_affected_by_rule(r
)) * objects_per_batch
;
565 vector
<float> batch_num_objects_expected( per
.size() );
567 for (unsigned i
= 0; i
< per
.size() ; i
++)
568 batch_num_objects_expected
[i
] = (proportional_weights
[i
]*batch_expected_objects
);
570 // create a vector to hold placement results temporarily
571 vector
<int> temporary_per ( per
.size() );
573 for (int x
= batch_min
; x
<= batch_max
; x
++) {
574 // create a vector to hold the results of a CRUSH placement or RNG simulation
579 err
<< "CRUSH"; // prepend CRUSH to placement output
582 real_x
= crush_hash32_2(CRUSH_HASH_RJENKINS1
, x
, (uint32_t)pool_id
);
584 crush
.do_rule(r
, real_x
, out
, nr
, weight
, 0);
587 err
<< "RNG"; // prepend RNG to placement output to denote simulation
588 // test our new monte carlo placement generator
589 random_placement(r
, out
, nr
, weight
);
593 err
<< " rule " << r
<< " x " << x
<< " " << out
<< std::endl
;
595 if (output_data_file
)
596 write_integer_indexed_vector_data_string(tester_data
.placement_information
, x
, out
);
598 bool has_item_none
= false;
599 for (unsigned i
= 0; i
< out
.size(); i
++) {
600 if (out
[i
] != CRUSH_ITEM_NONE
) {
602 temporary_per
[out
[i
]]++;
604 has_item_none
= true;
608 batch_per
[current_batch
] = temporary_per
;
610 if (output_bad_mappings
&&
611 (out
.size() != (unsigned)nr
||
613 err
<< "bad mapping rule " << r
<< " x " << x
<< " num_rep " << nr
<< " result " << out
<< std::endl
;
617 batch_min
= batch_max
+ 1;
618 batch_max
= batch_min
+ objects_per_batch
- 1;
621 for (unsigned i
= 0; i
< per
.size(); i
++)
622 if (output_utilization
&& !output_statistics
)
623 err
<< " device " << i
624 << ":\t" << per
[i
] << std::endl
;
626 for (map
<int,int>::iterator p
= sizes
.begin(); p
!= sizes
.end(); ++p
)
627 if (output_statistics
)
628 err
<< "rule " << r
<< " (" << crush
.get_rule_name(r
) << ") num_rep " << nr
629 << " result size == " << p
->first
<< ":\t"
630 << p
->second
<< "/" << (max_x
-min_x
+1) << std::endl
;
632 if (output_statistics
)
633 for (unsigned i
= 0; i
< per
.size(); i
++) {
634 if (output_utilization
) {
635 if (num_objects_expected
[i
] > 0 && per
[i
] > 0) {
636 err
<< " device " << i
<< ":\t"
637 << "\t" << " stored " << ": " << per
[i
]
638 << "\t" << " expected " << ": " << num_objects_expected
[i
]
641 } else if (output_utilization_all
) {
642 err
<< " device " << i
<< ":\t"
643 << "\t" << " stored " << ": " << per
[i
]
644 << "\t" << " expected " << ": " << num_objects_expected
[i
]
649 ldout(cct
, 20) << "output statistics created" << dendl
;
651 if (output_data_file
)
652 for (unsigned i
= 0; i
< per
.size(); i
++) {
653 vector_data_buffer_f
.clear();
654 vector_data_buffer_f
.push_back( (float) per
[i
]);
655 vector_data_buffer_f
.push_back( (float) num_objects_expected
[i
]);
657 write_integer_indexed_vector_data_string(tester_data
.device_utilization_all
, i
, vector_data_buffer_f
);
659 if (num_objects_expected
[i
] > 0 && per
[i
] > 0)
660 write_integer_indexed_vector_data_string(tester_data
.device_utilization
, i
, vector_data_buffer_f
);
663 if (output_data_file
&& num_batches
> 1) {
664 // stage batch utilization information for post-processing
665 for (int i
= 0; i
< num_batches
; i
++) {
666 write_integer_indexed_vector_data_string(tester_data
.batch_device_utilization_all
, i
, batch_per
[i
]);
667 write_integer_indexed_vector_data_string(tester_data
.batch_device_expected_utilization_all
, i
, batch_per
[i
]);
671 ldout(cct
, 20) << "output data file created" << dendl
;
672 string rule_tag
= crush
.get_rule_name(r
);
675 write_data_set_to_csv(output_data_file_name
+rule_tag
,tester_data
);
677 ldout(cct
, 20) << "successfully written csv" << dendl
;
681 if (output_choose_tries
) {
683 int n
= crush
.get_choose_profile(&v
);
684 for (int i
=0; i
<n
; i
++) {
685 cout
.setf(std::ios::right
);
687 << i
<< ": " << std::setw(9) << v
[i
];
688 cout
.unsetf(std::ios::right
);
692 crush
.stop_choose_profile();
698 int CrushTester::compare(CrushWrapper
& crush2
)
700 if (min_rule
< 0 || max_rule
< 0) {
702 max_rule
= crush
.get_max_rules() - 1;
704 if (min_x
< 0 || max_x
< 0) {
709 // initial osd weights
710 vector
<__u32
> weight
;
713 * note device weight is set by crushtool
714 * (likely due to a given a command line option)
716 for (int o
= 0; o
< crush
.get_max_devices(); o
++) {
717 if (device_weight
.count(o
)) {
718 weight
.push_back(device_weight
[o
]);
719 } else if (crush
.check_item_present(o
)) {
720 weight
.push_back(0x10000);
727 adjust_weights(weight
);
729 map
<int,int> bad_by_rule
;
732 for (int r
= min_rule
; r
< crush
.get_max_rules() && r
<= max_rule
; r
++) {
733 if (!crush
.rule_exists(r
)) {
734 if (output_statistics
)
735 err
<< "rule " << r
<< " dne" << std::endl
;
739 for (int nr
= min_rep
; nr
<= max_rep
; nr
++) {
740 for (int x
= min_x
; x
<= max_x
; ++x
) {
742 crush
.do_rule(r
, x
, out
, nr
, weight
, 0);
744 crush2
.do_rule(r
, x
, out2
, nr
, weight
, 0);
753 int max
= (max_rep
- min_rep
+ 1) * (max_x
- min_x
+ 1);
754 double ratio
= (double)bad
/ (double)max
;
755 cout
<< "rule " << r
<< " had " << bad
<< "/" << max
756 << " mismatched mappings (" << ratio
<< ")" << std::endl
;
759 cerr
<< "warning: maps are NOT equivalent" << std::endl
;
761 cout
<< "maps appear equivalent" << std::endl
;