условие цикла for вступает в силу только после достижения точки останова

Question

Я пытаюсь решить проблему с помощью hackerrank.

На данный момент мой код плохой и неправильный, но суть этого вопроса не в этом. Проблема в цикле for, состояние которого не всегда работает. Вот код:

#include <cassert>
#include <iostream>
#include <set>

using namespace std;

// Integer power.
long ipow(int x, int y)
{
    assert(x > 0);
    assert(y >= 0);

    long res = 1;
    while (y--)
        res *= x;
    return res;
}

std::set<int> compute_distinct_sequence_numbers(int n, int s, int p, int q)
{
    static_assert(sizeof(long) > 4, "long is assumed to be larger 4 bytes");

    set<int> distinct_numbers;
    const long max1 = ipow(2, 31);  // maximum plus 1

    // Compute first number of sequence.
    int prev = s % max1;
    distinct_numbers.emplace(prev);

    // Compute subsequent elements of sequence and put them in set.
    for (int i = 1; i < n; ++i) {
        prev = (prev * p + q) % max1;
        distinct_numbers.emplace(prev);
    }

    return distinct_numbers;
}

int main(int argc, char** argv)
{
    // Read numbers.
    int n, s, p, q;
    if (!(cin >> n >> s >> p >> q))
        throw std::runtime_error("error on input");;

    // Compute set containing distinct number of sequence.
    std::set<int> distinct_numbers = compute_distinct_sequence_numbers(n, s, p, q);

    // Print number of distinct numbers in sequence.
    cout << distinct_numbers.size() << std::endl;

    return 0;
} 

Если я запускаю программу с вводом «10000000 658061970 695098531 1430548937», это займет очень много времени (почти 20 секунд).

Основнойпроблема с этим заключается в том, что цикл не завершается, когда i достигает n. Когда я останавливаю программу в GDB, программа застревает в цикле, и i может иметь значение больше n.

Следующий сеанс GDB демонстрирует это:

(gdb) run
Starting program: /home/janosch/programming/hackerrank/cpp/main 
10000000 658061970 695098531 1430548937

Breakpoint 1, compute_distinct_sequence_numbers (n=10000000, s=658061970, p=695098531, q=1430548937) at main.cpp:32
32              prev = (prev * p + q) % max1;
(gdb) print i
$7 = 10000000
(gdb) info breakpoints 
Num     Type           Disp Enb Address            What
1       breakpoint     keep y   0x00000000004010c0 in compute_distinct_sequence_numbers(int, int, int, int) at main.cpp:32
        stop only if i = n
        breakpoint already hit 1 time
(gdb) n
33              distinct_numbers.emplace(prev);
(gdb) 
31          for (int i = 1; i < n; ++i) {
(gdb) 
36          return distinct_numbers;
(gdb) 
37      }

Я установил условную точку останова (i == n) на линии prev = (prev * p + q) % max1;. Обычно не должно быть возможности достичь этой точки останова, поскольку цикл должен завершиться до нажатия n. Даже если я использую намного более высокое значение для условной точки останова (например, i == 2*n), точка останова срабатывает.

Как только я достигну точки останова, программа немедленно выходит из цикла. Это верно для пошагового выполнения (команда GDB n) и продолжения (команда GDB c).

Вот мой супер простой Makefile:

CC = g++
CFLAGS = -Wall -std=c++14 -c -g
LDFLAGS = 

all:    main

main:   main.o
        $(CC) $(LDFLAGS) main.o -o main

main.o: main.cpp
        $(CC) $(CFLAGS) main.cpp

Программа работаетв Ubuntu 16.04.

Что я делаю не так? Как программа может вести себя по-разному при работе в GDB? Это кажется невероятно простым.

Answer 1

Как только я достиг точки останова, программа немедленно выходит из цикла.

Это экземпляр PEBKAC . Как заметил Марк Плотник, ваше условие точки останова - это не просто условие, а условие и присвоение.

Каждый раз, когда условие оценивается, i присваивается значение n, а затем результат оценивается по 0.

Это означает, что в отладчике с этой конкретной «условной» точкой останова ваш цикл выполняется ровно один раз.

Теперь, когда я не вообще присоединяю GDB, я наблюдаю:

$ g++ -g t.cc -O0 &&  echo "10000000 658061970 695098531 1430548937" | time ./a.out
10000000
18.15user 0.20system 0:18.36elapsed 99%CPU (0avgtext+0avgdata 472032maxresident)k
0inputs+0outputs (0major+117322minor)pagefaults 0swaps

$ g++ -g t.cc -O2 &&  echo "10000000 658061970 695098531 1430548937" | time ./a.out
10000000
12.09user 0.14system 0:12.27elapsed 99%CPU (0avgtext+0avgdata 472028maxresident)k
0inputs+0outputs (0major+117322minor)pagefaults 0swaps

, из чего можно сделать вывод, что программа медленная, потому что она выполняет 10 миллионов итераций, а не потому, что цикл forкак-то сломан.

Используя perf record и perf report, мы можем увидеть , где все это время потрачено:

# Samples: 50K of event 'cycles:uppp'
# Event count (approx.): 50290745010
#
# Overhead  Command  Shared Object        Symbol                                                                                                         
# ........  .......  ...................  ...............................................................................................................
#
    79.02%  a.out    a.out                [.] std::_Rb_tree<int, int, std::_Identity<int>, std::less<int>, std::allocator<int> >::_M_emplace_unique<int&>
     8.75%  a.out    a.out                [.] std::_Rb_tree<int, int, std::_Identity<int>, std::less<int>, std::allocator<int> >::_M_erase
     5.82%  a.out    libstdc++.so.6.0.25  [.] std::_Rb_tree_insert_and_rebalance
     0.93%  a.out    libstdc++.so.6.0.25  [.] 0x00000000000a9440
     0.89%  a.out    libc-2.28.so         [.] _int_malloc
     0.86%  a.out    libc-2.28.so         [.] cfree@GLIBC_2.2.5
     0.81%  a.out    a.out                [.] compute_distinct_sequence_numbers
     0.78%  a.out    libc-2.28.so         [.] _int_free