العد التنازلي في الحلقات

Question

أعتقد (من بعض القراءات البحثية) أن العد التنازلي في الحلقات هو في الواقع أكثر كفاءة وأسرع في وقت التشغيل.رمز البرنامج الكامل الخاص بي هو C++

لدي حاليا هذا:

for (i=0; i<domain; ++i) {

بلدي "أنا" غير موقعة int ، أيضا "المجال" غير موقعة int

في for-loop، يتم استخدام i للمرور عبر مصفوفة، على سبيل المثال.

array[i] = do stuff

يؤدي تحويل هذا إلى العد التنازلي إلى إفساد الإخراج المتوقع/الصحيح لروتيني.

أستطيع أن أتخيل أن الإجابة تافهة للغاية، لكن لا أستطيع أن أستوعبها.

تحديث:لا يعتمد "القيام بالأشياء" على التكرار السابق أو اللاحق.الحسابات داخل الحلقة مستقلة عن تكرار i.(وآمل أن يجعل الشعور).

تحديث:لتحقيق تسريع وقت التشغيل باستخدام حلقة for-loop الخاصة بي، هل أقوم بالعد التنازلي وإذا كان الأمر كذلك، قم بإزالة الجزء غير الموقع عند حذف int الخاص بي، أو ما هي الطريقة الأخرى؟

الرجاء المساعدة.

Answer 1

أعتقد أن حلقة Back for الخاصة بك تبدو كما يلي:

for (i = domain - 1; i >= 0; --i) {

في هذه الحالة، لأن i يكون غير موقعة, ، فإنه سوف دائماً تكون أكبر من أو تساوي الصفر.عندما تقوم بتقليل متغير غير موقّع يساوي صفر، فإنه سوف يلتف حول رقم كبير جدًا.الحل إما أن تصنع i تم التوقيع، أو قم بتغيير الحالة في حلقة for مثل هذا:

for (i = domain - 1; i >= 0 && i < domain; --i) {

أو العد من domain ل 1 وليس من domain - 1 ل 0:

for (i = domain; i >= 1; --i) {
    array[i - 1] = ...; // notice you have to subtract 1 from i inside the loop now
}

Answer 2

وهناك طريقة صحيحة واحدة فقط من حلقات الوراء باستخدام عداد غير موقعة:

for( i = n; i-- > 0; )
{
    // Use i as normal here
}

وهناك خدعة هنا، للحلقة الأخيرة التكرار سيكون لديك ط = 1 في الجزء العلوي من الحلقة، i--> 0 يمر ل1> 0، ثم ط = 0 في الجسم حلقة. على التكرار التالي i--> 0 فشل لأنني == 0، لذلك لا يهم أن إنقاص بوستفيكس توالت دون وصفة طبية.

وغير واضح جدا وأنا أعلم.

Answer 3

وهذه ليست إجابة لمشكلتك، لأنك لا يبدو أن لديها مشكلة.

وهذا النوع من الأمثل هو غير ذي صلة تماما، وينبغي أن تترك للمترجم (إذا فعلت على الإطلاق).

هل لمحة عن البرنامج للتأكد من أن لديك للحلقة هو عنق الزجاجة؟ إن لم يكن، فإنك لا تحتاج إلى قضاء بعض الوقت في القلق حول هذا الموضوع. بل أكثر من ذلك، وجود "أنا" كما كثافة العمليات "تسجيل"، كما تكتب، لا معنى الحقيقي من وجهة نظر الأداء.

وحتى من دون معرفة نطاق مشكلتك، استطيع ان اؤكد لكم ان كل من تقنية حلقات الاتجاه المعاكس و "تسجيل" مكافحة كثافة العمليات سيكون <م> يذكر تأثير على أداء البرنامج الخاص بك. تذكر، "من السابق لأوانه الأمثل هو أصل كل الشرور".

وقال ذلك، سيكون الوقت الأمثل قضى أفضل أن يكون على التفكير في الهيكل العام البرنامج، وهياكل البيانات والخوارزميات المستخدمة، واستخدام الموارد، الخ.

Answer 4

وفحص لمعرفة ما اذا كان الرقم صفر يمكن أن يكون أسرع أو أكثر فعالية من المقارنة. ولكن هذا هو نوع من التحسين الجزئي كنت حقا لا ينبغي أن تقلق - عدد قليل من الدورات على مدار الساعة وسوف تتضاءل إلى حد كبير فقط حول أي قضية الأداء الإقتصادي الأداء الأخرى

في إلى x86:

dec eax
jnz Foo

وبدلا من:

inc eax
cmp eax, 15
jl Foo

Answer 5

إذا كان لديك مترجم لائق، وسوف تحسين "العد حتى" بنفس فعالية "العد التنازلي". مجرد محاولة مؤشرات قليلة وسترى.

Answer 6

وهكذا أنت "قراءة" أن couting أسفل هو أكثر كفاءة؟ أجد أن هذا من الصعب جدا أن نصدق ما لم تريني بعض النتائج التعريف ورمز. يمكنني شرائه في بعض الظروف، ولكن في الحالة العامة، لا. يبدو لي أن هذا هو حالة كلاسيكية من التحسين سابق لأوانه.

وتعليقك حول "تسجيل كثافة العمليات ط" هو أيضا تعبيرا جدا. في الوقت الحاضر، ومترجم يعرف دائما أفضل مما كنت كيفية تخصيص سجلات. لا تهتم باستخدام باستخدام الكلمة السجل إلا إذا كنت قد لمحة التعليمات البرمجية.

Answer 7

وعندما كنت حلقات من خلال هياكل البيانات من أي نوع، يفتقد مخبأ لها تأثير أكبر بكثير من الاتجاه الذي تسير. تشغل نفسك مع الصورة الأكبر لتخطيط الذاكرة وبنية خوارزمية بدلا من تافهة تحقيق أمثلية الصغيرة.

Answer 8

لا علاقة له بالعد أعلى أو تحت.ما يمكن أن يكون أسرع هو العد نحو الصفر. إجابة مايكل يوضح السبب - يمنحك الإصدار x86 مقارنة بالصفر كأثر جانبي ضمني للعديد من التعليمات، لذلك بعد ضبط العداد الخاص بك، ما عليك سوى التفرع بناءً على النتيجة بدلاً من إجراء مقارنة صريحة.(ربما تقوم معماريات أخرى بذلك أيضًا؛لا أعرف.)

تشتهر مترجمات بورلاند باسكال بأداء هذا التحسين.يقوم المترجم بتحويل هذا الكود:

for i := x to y do
  foo(i);

إلى تمثيل داخلي أقرب إلى هذا:

tmp := Succ(y - x);
i := x;
while tmp > 0 do begin
  foo(i);
  Inc(i);
  Dec(tmp);
end;

(أقول سيئة السمعة ليس لأن التحسين يؤثر على نتيجة الحلقة، ولكن لأن مصحح الأخطاء يعرض متغير العداد بشكل غير صحيح.عندما يتفقد المبرمج i, ، قد يعرض مصحح الأخطاء قيمة tmp بدلاً من ذلك، لا يسبب أي نهاية للارتباك والذعر للمبرمجين الذين يعتقدون أن حلقاتهم تعمل بشكل عكسي.)

والفكرة هي أنه حتى مع اضافية Inc أو Dec التعليمات، فإنه لا يزال يمثل فوزًا صافيًا، من حيث وقت التشغيل، على إجراء مقارنة صريحة. ما إذا كان يمكنك في الواقع يلاحظ هذا الاختلاف مطروح للنقاش.

لكن لاحظ أن التحويل هو شيء سيفعله المترجم تلقائيا, ، بناءً على ما إذا كانت تعتبر التحول جديرًا بالاهتمام. عادةً ما يكون المترجم أفضل منك في تحسين التعليمات البرمجية، لذا لا تبذل الكثير من الجهد في التنافس معه.

على أية حال، لقد سألت عن C++، وليس باسكال.حلقات "for" C++ ليست سهلة تمامًا لتطبيق هذا التحسين عليها مثل حلقات Pascal "for" لأن حدود حلقات Pascal يتم دائمًا حسابها بالكامل قبل تشغيل الحلقة، بينما تعتمد حلقات C++ أحيانًا على حالة التوقف والحلقة محتويات.يحتاج مترجمو C++ إلى إجراء قدر من التحليل الثابت لتحديد ما إذا كانت أي حلقة معينة يمكن أن تناسب متطلبات نوع التحويل الذي تتأهل له حلقات باسكال دون قيد أو شرط.إذا قام مترجم C++ بالتحليل، فيمكنه إجراء تحويل مماثل.

لا يوجد ما يمنعك من كتابة حلقاتك بهذه الطريقة بنفسك:

for (unsigned i = 0, tmp = domain; tmp > 0; ++i, --tmp)
  array[i] = do stuff

افعل ذلك قد جعل التعليمات البرمجية الخاصة بك تعمل بشكل أسرع.كما قلت من قبل، على الرغم من أنك ربما لن تلاحظ.التكلفة الأكبر التي تدفعها عن طريق ترتيب حلقاتك يدويًا بهذه الطريقة هي أن التعليمات البرمجية الخاصة بك لم تعد تتبع المصطلحات الراسخة.حلقتك هي حلقة "for" عادية تمامًا، لكنها لم تعد كذلك تبدو مثل واحد - يحتوي على متغيرين، يتم العد في اتجاهين متعاكسين، ولا يتم استخدام أحدهما حتى في نص الحلقة - لذا فإن أي شخص يقرأ الكود الخاص بك (بما في ذلك أنت، أو أسبوع، أو شهر، أو عام من الآن عندما تنسى "التحسين" الذي كنت تأمل في تحقيقه) ستحتاج إلى بذل جهد إضافي لتثبت لنفسك أن الحلقة هي في الواقع حلقة عادية مقنعة.

(هل لاحظت أن الكود الخاص بي أعلاه يستخدم متغيرات غير موقعة مع عدم وجود خطر الالتفاف عند الصفر؟استخدام متغيرين منفصلين يسمح بذلك.)

ثلاثة أشياء يجب التخلص منها من كل هذا:

1. دع المحسن يقوم بعمله؛على العموم فهو أفضل منك في ذلك.
2. اجعل التعليمات البرمجية العادية تبدو عادية حتى لا تضطر التعليمات البرمجية الخاصة إلى التنافس لجذب انتباه الأشخاص الذين يقومون بمراجعتها أو تصحيح أخطائها أو صيانتها.
3. لا تفعل أي شيء خيالي باسم الأداء حتى يظهر الاختبار والتنميط أنه ضروري.

Answer 9

يمكنك محاولة ما يلي، الذي مترجم وتحسين كفاءة جدا:

#define for_range(_type, _param, _A1, _B1) \
    for (_type _param = _A1, _finish = _B1,\
    _step = static_cast<_type>(2*(((int)_finish)>(int)_param)-1),\
    _stop = static_cast<_type>(((int)_finish)+(int)_step); _param != _stop; \
_param = static_cast<_type>(((int)_param)+(int)_step))

والآن يمكنك استخدام ما يلي:

for_range (unsigned, i, 10,0)
{
    cout << "backwards i: " << i << endl;
}

for_range (char, c, 'z','a')
{
    cout << c << endl;
}

enum Count { zero, one, two, three }; 

for_range (Count, c, three, zero)
{
    cout << "backwards: " << c << endl;
}

وتستطيع تكرار في أي اتجاه:

for_range (Count, c, zero, three)
{
    cout << "forward: " << c << endl;
}

وحلقة

for_range (unsigned,i,b,a)
{
   // body of the loop
}

وسوف تنتج التعليمة البرمجية التالية:

 mov esi,b
L1:
;    body of the loop
   dec esi
   cmp esi,a-1
   jne L1 

Answer 10

ومن الصعب القول مع المعلومات المعطاة ولكن ... عكس مجموعة الخاصة بك، والعد التنازلي؟

Answer 11

أشار جيريمي روتين بحق إلى أن استخدام عداد حلقة غير موقعة أمر خطير.كما أنه غير ضروري، على حد علمي.

وأشار آخرون أيضًا إلى مخاطر التحسين المبكر.إنهم على حق تماما.

مع ذلك، هذا هو الأسلوب الذي استخدمته عند برمجة الأنظمة المضمنة منذ سنوات عديدة، عندما كان كل بايت وكل دورة ذات أهمية لشيء ما.هذه الأشكال كان مفيد بالنسبة لي في وحدات المعالجة المركزية والمترجمات المعينة التي كنت أستخدمها، ولكن قد يختلف عدد الأميال المقطوعة.

// Start out pointing to the last elem in array
pointer_to_array_elem_type p = array + (domain - 1);
for (int i = domain - 1; --i >= 0 ; ) {
     *p-- = (... whatever ...)
}

يستفيد هذا النموذج من علامة الشرط التي تم تعيينها بعض المعالجات بعد العمليات الحسابية - في بعض البنيات، يمكن دمج التناقص والاختبار لحالة الفرع في تعليمات واحدة.لاحظ أن استخدام التخفيض المسبق (--i) هو المفتاح هنا - باستخدام postdecrement (i--) لن تعمل كذلك.

بدلاً عن ذلك،

// Start out pointing *beyond* the last elem in array
pointer_to_array_elem_type p = array + domain;
for (pointer_to_array_type p = array + domain; p - domain > 0 ; ) {
     *(--p) = (... whatever ...)
}

يستفيد هذا النموذج الثاني من حساب المؤشر (العنوان).نادرا ما أرى النموذج (pointer - int) هذه الأيام (لسبب وجيه)، ولكن اللغة تضمن أنه عند طرح int من المؤشر، يتم تقليل المؤشر بمقدار (int * sizeof (*pointer)).

سأؤكد مرة أخرى أن نجاح هذه النماذج يعتمد على وحدة المعالجة المركزية والمترجم الذي تستخدمه.لقد خدموني جيدًا في معماريات موتورولا 6809 و68000.

Answer 12

في بعض احق النوى الذراع، إنقاص ومقارنة يستغرق سوى تعليمة واحدة. وهذا يجعل decrementing حلقات أكثر كفاءة من تزايد منها.

وأنا لا أعرف لماذا لم يكن هناك تعليمات-زيادة مقارنة أيضا.

وأنا مندهش أن هذا المنصب كان صوت -1 عندما انها قضية حقيقية.

Answer 13

الجميع هنا يركز على الأداء.يوجد في الواقع سبب منطقي للتكرار نحو الصفر والذي يمكن أن يؤدي إلى كود أنظف.

يعد التكرار على العنصر الأخير أولاً أمرًا مناسبًا عند حذف العناصر غير الصالحة عن طريق التبديل مع نهاية المصفوفة.بالنسبة للعناصر السيئة غير المتاخمة للنهاية، يمكننا التبديل إلى موضع النهاية، وتقليل حد نهاية المصفوفة، والاستمرار في التكرار.إذا كنت تكرر في النهاية، فإن التبديل مع النهاية قد يؤدي إلى تبديل السيئ بالسيء.من خلال التكرار من النهاية إلى 0، نعلم أن العنصر الموجود في نهاية المصفوفة قد تم بالفعل إثبات صلاحيته لهذا التكرار.

ولمزيد من التوضيح...

لو:

1. يمكنك حذف العناصر السيئة عن طريق التبديل مع أحد طرفي المصفوفة وتغيير حدود المصفوفة لاستبعاد العناصر السيئة.

ثم من الواضح:

2. يمكنك المبادلة بعنصر جيد أي.الذي تم اختباره بالفعل في هذا التكرار.

لذلك هذا يعني:

3. إذا قمنا بالتكرار بعيدًا عن حد المتغير، فقد ثبت أن العناصر الموجودة بين حد المتغير ومؤشر التكرار الحالي جيدة.سواء حصل مؤشر التكرار على ++ أو -- لا يهم.ما يهم هو أننا نقوم بالتكرار بعيدًا عن حدود المتغير حتى نعرف أن العناصر المجاورة له جيدة.

حتى النهاية:

4. يتيح لنا التكرار نحو 0 استخدام متغير واحد فقط لتمثيل حدود المصفوفة.ما إذا كان هذا مهمًا هو قرار شخصي بينك وبين المترجم الخاص بك.

Answer 14

ما يهم أكثر بكثير من ما إذا كنت بالزيادة أو النقصان مكافحة الخاص بك أم لا وأنت تسير الذاكرة أو لأسفل الذاكرة. هي الأمثل معظم مخابئ للذهاب الذاكرة، وليس إلى أسفل الذاكرة. منذ زمن الوصول إلى الذاكرة هو عنق الزجاجة أن معظم برامج اليوم وجهه، وهذا يعني أن تغيير البرنامج بحيث تذهب الذاكرة يمكن أن يؤدي إلى تعزيز الأداء حتى لو كان هذا يتطلب مقارنة العداد الخاص بك إلى قيمة غير صفرية. في بعض البرامج الخاصة بي، رأيت تحسن كبير في الأداء من خلال تغيير قانون بلدي لترتفع الذاكرة بدلا من أسفل ذلك.

ومشكك؟ وهنا الإخراج التي حصلت على:

sum up   = 705046256
sum down = 705046256
Ave. Up Memory   = 4839 mus
Ave. Down Memory =  5552 mus
sum up   = inf
sum down = inf
Ave. Up Memory   = 18638 mus
Ave. Down Memory =  19053 mus

ومن تشغيل هذا البرنامج:

#include <chrono>
#include <iostream>
#include <random>
#include <vector>

template<class Iterator, typename T>
void FillWithRandomNumbers(Iterator start, Iterator one_past_end, T a, T b) {
  std::random_device rnd_device;
  std::mt19937 generator(rnd_device());
  std::uniform_int_distribution<T> dist(a, b);
  for (auto it = start; it != one_past_end; it++)
    *it = dist(generator);
  return ;
}

template<class Iterator>
void FillWithRandomNumbers(Iterator start, Iterator one_past_end, double a, double b) {
  std::random_device rnd_device;
  std::mt19937_64 generator(rnd_device());
  std::uniform_real_distribution<double> dist(a, b);
  for (auto it = start; it != one_past_end; it++)
    *it = dist(generator);
  return ;
}

template<class RAI, class T>
inline void sum_abs_up(RAI first, RAI one_past_last, T &total) {
  T sum = 0;
  auto it = first;
  do {
    sum += *it;
    it++;
  } while (it != one_past_last);
  total += sum;
}

template<class RAI, class T>
inline void sum_abs_down(RAI first, RAI one_past_last, T &total) {
  T sum = 0;
  auto it = one_past_last;
  do {
    it--;
    sum += *it;
  } while (it != first);
  total += sum;
}

template<class T> std::chrono::nanoseconds TimeDown(
                      std::vector<T> &vec, const std::vector<T> &vec_original,
                      std::size_t num_repititions, T &running_sum) {
  std::chrono::nanoseconds total{0};
  for (std::size_t i = 0; i < num_repititions; i++) {
    auto start_time = std::chrono::high_resolution_clock::now();
    sum_abs_down(vec.begin(), vec.end(), running_sum);
    total += std::chrono::high_resolution_clock::now() - start_time;
    vec = vec_original;
  }
  return total;
}

template<class T> std::chrono::nanoseconds TimeUp(
                      std::vector<T> &vec, const std::vector<T> &vec_original,
                      std::size_t num_repititions, T &running_sum) {
  std::chrono::nanoseconds total{0};
  for (std::size_t i = 0; i < num_repititions; i++) {
    auto start_time = std::chrono::high_resolution_clock::now();
    sum_abs_up(vec.begin(), vec.end(), running_sum);
    total += std::chrono::high_resolution_clock::now() - start_time;
    vec = vec_original;
  }
  return total;
}

int main() {
  std::size_t num_repititions = 1 << 10;
  {
  typedef int ValueType;
  auto lower = std::numeric_limits<ValueType>::min();
  auto upper = std::numeric_limits<ValueType>::max();
  std::vector<ValueType> vec(1 << 24);

  FillWithRandomNumbers(vec.begin(), vec.end(), lower, upper);
  const auto vec_original = vec;
  ValueType sum_up = 0, sum_down = 0;

  auto time_up = TimeUp(vec, vec_original, num_repititions, sum_up).count();
  auto time_down = TimeDown(vec, vec_original, num_repititions, sum_down).count();
  std::cout << "sum up   = " << sum_up   << '\n';
  std::cout << "sum down = " << sum_down << '\n';
  std::cout << "Ave. Up Memory   = " << time_up/(num_repititions * 1000) << " mus\n";
  std::cout << "Ave. Down Memory =  "<< time_down/(num_repititions * 1000) << " mus"
            << std::endl;
  }
  {
  typedef double ValueType;
  auto lower = std::numeric_limits<ValueType>::min();
  auto upper = std::numeric_limits<ValueType>::max();
  std::vector<ValueType> vec(1 << 24);

  FillWithRandomNumbers(vec.begin(), vec.end(), lower, upper);
  const auto vec_original = vec;
  ValueType sum_up = 0, sum_down = 0;

  auto time_up = TimeUp(vec, vec_original, num_repititions, sum_up).count();
  auto time_down = TimeDown(vec, vec_original, num_repititions, sum_down).count();
  std::cout << "sum up   = " << sum_up   << '\n';
  std::cout << "sum down = " << sum_down << '\n';
  std::cout << "Ave. Up Memory   = " << time_up/(num_repititions * 1000) << " mus\n";
  std::cout << "Ave. Down Memory =  "<< time_down/(num_repititions * 1000) << " mus"
            << std::endl;
  }
  return 0;
}

وكلا sum_abs_up وsum_abs_down تفعل الشيء نفسه وتوقيت أنها بنفس الطريقة مع الفرق الوحيد هو أن sum_abs_up ترتفع الذاكرة أثناء sum_abs_down تنخفض الذاكرة. حتى أمرر vec بالرجوع بحيث أن كلا من وظائف الوصول إلى مواقع الذاكرة نفسها. ومع ذلك، sum_abs_up هو أسرع باستمرار من sum_abs_down. إعطائها المدى نفسك (أنا جمعت مع ز ++ -O3).

ومعلوماتك vec_original هناك للتجريب، لتجعل من السهل بالنسبة لي لتغيير sum_abs_up وsum_abs_down بطريقة يجعلها تغير vec في حين لا تسمح هذه التغييرات تؤثر توقيت المستقبلية.

ومن المهم أن نلاحظ كيف ضيق الحلقة أنني التوقيت. إذا الجسم حلقة هو كبير فإنه من المحتمل أن لا يهم ما إذا كان مكرر لها يذهب صعودا أو هبوطا الذاكرة منذ الوقت الذي يستغرقه تنفيذ إرادة هيئة حلقة من المحتمل أن تهيمن تماما. أيضا، من المهم أن نذكر أن بعض الحلقات نادرة، نزول الذاكرة أسرع أحيانا من الصعود عليه. ولكن حتى مع هذه الحلقات انها نادرا ما الحالة التي تصل دائما أبطأ من الذهاب إلى أسفل (على عكس الحلقات التي ترتفع الذاكرة، والتي هي في كثير من الأحيان دائما أسرع من أي ما يعادل أسفل الذاكرة حلقات، حفنة صغيرة من المرات كانوا حتى 40 +٪ أسرع).

وهذه النقطة هي، وكقاعدة عامة، إذا كان لديك الخيار، إذا الجسم الحلقة هو صغير، وإذا كان هناك فارق كبير بين وجود حلقة الخاص بك ترتفع الذاكرة بدلا من الأسفل، ثم يجب عليك ان تذهب الذاكرة.