From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 16505 invoked by alias); 30 Oct 2009 19:07:57 -0000 Received: (qmail 16473 invoked by uid 48); 30 Oct 2009 19:07:44 -0000 Date: Fri, 30 Oct 2009 19:07:00 -0000 Message-ID: <20091030190744.16472.qmail@sourceware.org> X-Bugzilla-Reason: CC References: Subject: [Bug libstdc++/41351] std::rotate on RAI does not conform to ISO complexity requirement In-Reply-To: Reply-To: gcc-bugzilla@gcc.gnu.org To: gcc-bugs@gcc.gnu.org From: "potswa at mac dot com" Mailing-List: contact gcc-bugs-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Archive: List-Post: List-Help: Sender: gcc-bugs-owner@gcc.gnu.org X-SW-Source: 2009-10/txt/msg02563.txt.bz2 ------- Comment #41 from potswa at mac dot com 2009-10-30 19:07 ------- Created an attachment (id=18934) --> (http://gcc.gnu.org/bugzilla/attachment.cgi?id=18934&action=view) table of benchmarks comparing various algorithms and parameters As the Euclidean ring division algorithm sweeps the memory range at least once per ring, you can see from this table that the present RAI implementation performs very poorly for small k greater than one. The final row, "fwd +copy", is a new proposal which adds the std::copy calls to the existing forward iterator algo. It remains compatible with bidirectional iterators and, from this data, looks pretty good. Its moderately bad showing in the final column I don't yet understand. The special cases for left and right by one should use std::move and std::move_backward, respectively, I guess. I'm not sure what state of testing I left things at before, but let's look at the performance numbers first. -- http://gcc.gnu.org/bugzilla/show_bug.cgi?id=41351