mpqsStatistics.cc

Go to the documentation of this file.
00001 
00007 
00008 namespace statistical_data
00009 {
00010 
00011  class CDynamicFactorRating
00012   {
00013    private:
00014     static const int mysize = 7;
00015     int distribution[mysize];
00016     /* for statistical evaluation on how the dynamic factorbase
00017        is responsible for the finding of relations:
00018         [0]-> no dynamic factor is involved,
00019         [1]-> one dynamic factor is involved
00020         [2]-> two dynamic factors are involved
00021         [3]-> three dynamic factors are involved
00022         [n]-> n dynamic factors are involved
00023         [mysize-1]-> at least mysize-1 dynamic factors are involved
00024      */
00025 
00026    public:
00027     CDynamicFactorRating()
00028     {
00029       for (int i=0; i<mysize; ++i) distribution[i]=0;
00030     }
00031     ~CDynamicFactorRating() { }
00032 
00033     int size() const
00034     {
00035       return mysize;
00036     }
00037 
00038     int entry(const int pos) const
00039     {
00040       return distribution[pos];
00041     }
00042 
00043     void increment_Hits_at_position(const int pos)
00044     {
00045       if (pos<size()) ++distribution[pos]; else ++distribution[size()-1];
00046     }
00047   };    
00048 
00049  CDynamicFactorRating DynamicFactorRating;
00050  int directly_sieved_DynamicFactors = 0;
00051  int directly_sieved_SpecialFactors = 0;
00052  unsigned int relations_sieved_so_far = 0; // total counter
00053 
00054 #ifndef IS_CLIENT
00055  // the following statistical data can only be collected during
00056  // a detailed analysis of the relations. Therefore these data
00057  // are restricted to servers and stand-alone versions.
00058  
00059  // Whenever it is possible, DynamicFactorRating is also updated.
00060  // Due to program restrictions/complexity, some "special hits" are
00061  // not counted accurately in DynamicFactorRating. (But only stats are affected!) 
00062 
00063  int Special_hit = 0;
00064  int Special_to_dynamic_Factor_hit = 0;
00065  int DLP_cycle_hits = 0;
00066 #endif
00067 
00068 #ifdef IS_SERVER
00069  // only for a server: collect statistical data about clients
00070 
00071  class CClientStats : protected CmpqsFactortypes
00072  {
00073   private:
00074    static CMutex Mutex;
00075    static unsigned int overall_counter[Factortype_size];
00076    unsigned int counter[Factortype_size];
00077    time_t first_connect, timestamp;
00078   protected:
00079    static void lock() { Mutex.lock(); }
00080    static void unlock() { Mutex.unlock(); }
00081   public:
00082 
00083    CClientStats() : counter(), first_connect(time(NULL)), timestamp(0) { }
00084    ~CClientStats() { }
00085 
00086    void PutTimeStamp(const time_t t = time(NULL))
00087    {
00088      lock();
00089      timestamp=t;
00090      unlock();
00091    }
00092 
00094    void increment(const CmpqsFactortypes::Factortype FType)
00095    {
00096      lock();
00097      ++counter[FType]; ++overall_counter[FType];
00098      unlock();  
00099    }
00100   
00101    const string info() const
00102    {
00103      ostringstream os;
00104      char buf [32];
00105      lock();
00106      const double percentage =
00107       100.0*static_cast<double>(counter[static_prime]+counter[single_large_prime]+counter[double_large_prime])
00108        /static_cast<double>(overall_counter[static_prime]+overall_counter[single_large_prime]+overall_counter[double_large_prime]);
00109      ctime_r(&first_connect,buf); // get localtime string for first_connect
00110      //buf[24]='\0'; // get rid of trailing newline
00111      buf[16]='\0'; // cut seconds, year and trailing newline
00112      char* const datestr = &buf[4]; // be less verbose
00113      os << datestr << " - ";
00114      ctime_r(&timestamp,buf);
00115      buf[16]='\0'; // cut seconds, year and trailing newline
00116      os << datestr << ":"
00117         << setw(5) << counter[static_prime] << ","
00118         << setw(7) << counter[single_large_prime] << ","
00119         << setw(8) << counter[double_large_prime] << "|";
00120      os.setf(ios::right, ios::adjustfield);
00121      os.setf(ios::fixed, ios::floatfield);
00122      os << setw(5) << setprecision(1) << percentage << "%" << flush;
00123      unlock();
00124      return os.str();
00125    }
00126 
00127    const string XML_info() const
00128    {
00129      ostringstream os;
00130      char buf [32];
00131      lock();
00132      const double percentage =
00133       100.0*static_cast<double>(counter[static_prime]+counter[single_large_prime]+counter[double_large_prime])
00134        /static_cast<double>(overall_counter[static_prime]+overall_counter[single_large_prime]+overall_counter[double_large_prime]);
00135      ctime_r(&first_connect,buf); // get localtime string for first_connect
00136      //buf[24]='\0'; // get rid of trailing newline
00137      buf[16]='\0'; // cut seconds, year and trailing newline
00138      char* const datestr = &buf[4]; // be less verbose
00139      os << " FIRSTCONNECT=\"" << datestr << "\"";
00140      ctime_r(&timestamp,buf);
00141      buf[16]='\0'; // cut seconds, year and trailing newline
00142      os << " LASTCONNECT=\"" << datestr << "\""
00143         << " STATICRELATIONS=\"" << counter[static_prime] << "\""
00144         << " DYNAMICRELATIONS=\"" << counter[single_large_prime] << "\""
00145         << " DLPRELATIONS=\"" << counter[double_large_prime] << "\"";
00146      os.setf(ios::right, ios::adjustfield);
00147      os.setf(ios::fixed, ios::floatfield);
00148      os << " PERCENTAGE=\"" << setw(6) << setprecision(2) << percentage
00149         << "%" << "\"" << flush;
00150      unlock();
00151      return os.str();
00152    }
00153 
00154  };
00155  CMutex CClientStats::Mutex;
00156  unsigned int CClientStats::overall_counter[Factortype_size] = {0};
00157 
00158  typedef map<string,CClientStats> TAllClientStats;
00159  TAllClientStats AllClientStats; // this is a list of all clients ever connected to the server
00160  CMutex AllClientStats_Mutex;
00161 
00162 #endif /* IS_SERVER */
00163 
00164  class CProgressStats : private ForbidAssignment
00165   {
00166    private:
00167     double granularity;
00168     double next_sample_d;
00169     int next_sample_at;
00170 
00171     class TSample
00172      {
00173       private:
00174        unsigned int static_relations, SLP_relations, DLP_relations;
00175        time_t Time;
00176       public:
00177 #ifdef IS_CLIENT
00178        TSample() : static_relations(StaticRelations::Count()),
00179           SLP_relations(DynamicFactorRelations.size()),
00180           DLP_relations(directly_sieved_SpecialFactors), Time(time(NULL)) { }
00181 #else
00182        TSample() : static_relations(StaticRelations::Count()),
00183           SLP_relations(DynamicFactorRelations.size()),
00184           DLP_relations(SpecialRelations::Count()), Time(time(NULL)) { }
00185 #endif
00186 
00187        ~TSample() { }
00188        time_t get_Time() const { return Time; }
00189 
00190        void XML(std::ostream &os, const time_t PrevTime) const
00191         {
00192           os << "<tr>"
00193              << "<td>" << setw(5) << setprecision(4) << 100.0*static_cast<double>(static_relations)/static_cast<double>(StaticFactorbase::Size()) << "%</td>"
00194              << "<td>" << static_relations << "</td>"
00195              << "<td>" << SLP_relations << "</td>"
00196              << "<td>" << DLP_relations << "</td>"
00197              << "<td><TIMESTAMP TIME=\"" << get_Time() << "\" /></td>"
00198              << "<td><DIFFTIME TIME=\"" << get_Time()-PrevTime << "\" /></td>"
00199              << "</tr>";
00200         }
00201      };
00202 
00203     typedef std::vector<TSample> TSamples;
00204     TSamples Samples;
00205 
00206    public:
00207     explicit CProgressStats(const double _granularity = 0.01)
00208      : granularity(_granularity), next_sample_d(0.0), next_sample_at(0) { }
00209 
00210     ~CProgressStats() { }
00211 
00212    public:
00213     void take_sample()
00214      {
00215        if (StaticRelations::Count()<next_sample_at) return;
00216        Samples.push_back(TSample()); // create & append new sample
00217        do {
00218          next_sample_d += granularity;
00219          next_sample_at = static_cast<int>(round(StaticFactorbase::Size()*next_sample_d));
00220         } while (next_sample_at<StaticRelations::Count());
00221      }
00222 
00223     void XML(std::ostream &os) const
00224      {
00225        if (Samples.empty()) return;
00226        os << "<TABLE CONTENT=\"progress\" >" << endl;
00227        os << "<tr><td>Rate</td><td>Static Relations</td><td>SLP Relations</td><td>DLP Relations</td><td>Time</td><td>Difftime</td></tr>" << endl;
00228 
00229        time_t prevTime = Samples.begin()->get_Time();
00230        for (TSamples::const_iterator pos=Samples.begin(); pos!=Samples.end(); ++pos)
00231         {
00232           pos->XML(os,prevTime); os << endl;
00233           prevTime=pos->get_Time();
00234         }
00235        if (time(NULL)>prevTime+5)
00236         {
00237           // use a temporary sample to emit current state
00238           TSample().XML(os,prevTime); os << endl;
00239         }
00240        os << "</TABLE>" << endl;
00241      }
00242   };
00243 
00244  CProgressStats ProgressStats;
00245 
00246  time_t StartTimestamp = 0; // time, at which sieving got started
00247  time_t PreviousTimestamp = 0; // time, at which previous status message was issued
00248  int StartFilling; // filling of the equation system when sieving (re-)started
00249  struct tsample { time_t Zeitpunkt; int Filling; int total_sieved; };
00250  const int samples=1<<4;
00251  tsample sample[samples]; int i_newest_sample=0;
00252 
00253  void calc_ETA(void)
00254  {
00255    // Actually it is rather the average time to find the relations (based on
00256    // the current speed) than an accurate estimation of the remaining time
00257    // to arrival that is calculated in this function...
00258    // Extrapolating the intermediate results is quite difficult and almost
00259    // impossible. In a multiuser and multitasking system with a changing
00260    // number of clients you cannot foresee what will happen in the future. 
00261    // (If any fileclients are connected, the situation would become even
00262    // more complicated!)
00263 
00264    if (StaticRelations::Count()==StartFilling) return;
00265 
00266    /*
00267       now.x - old.x = delta.x  // relations
00268       now.y - old.y = delta.y  // time
00269       delta.y/delta.x = y per x  -> seconds per static relation
00270 
00271       wanted.x = missing relations = StaticFactorbase::Size() - StaticRelations::Count(); known
00272       wanted.y -> (estimated) time till arrival; to compute
00273 
00274       wanted.y = (delta.y/delta.x)*wanted.x
00275       ETA = estimated time of arrival = now.y + wanted.y
00276 
00277    */
00278 
00279 #ifdef VERBOSE_INFO
00280    const time_t now=time(NULL);
00281    const int i_oldest_sample=(i_newest_sample+1)%samples;
00282    double t=difftime(now,sample[i_oldest_sample].Zeitpunkt);
00283    t/=static_cast<double>(StaticRelations::Count()-sample[i_oldest_sample].Filling);
00284    double Restzeit=(StaticFactorbase::Size()-StaticRelations::Count())*t;
00285 
00286    {
00287      // print estimated time of arrival
00288      char buf[32]; struct tm my_tm;
00289      const time_t eta = now+static_cast<time_t>(Restzeit);
00290      localtime_r(&eta,&my_tm); asctime_r(&my_tm,buf);
00291      buf[24]='\0'; // get rid of trailing newline
00292      cout_status << "ETA: " << buf << ", ";
00293    }
00294    {
00295      double days = floor(Restzeit/(60*60*24));
00296      int hours,mins,secs;
00297      Restzeit=fmod(Restzeit,60*60*24);
00298      secs=static_cast<int>(Restzeit); mins=secs/60; hours=mins/60;
00299      mins%=60; secs%=60;
00300 
00301      if (days)
00302       cout_status << "time left (estimated): " << days << "d " << hours << "h" << endl;
00303      else
00304       cout_status << "time left (estimated): " << hours << "h " << mins << "m "
00305                   << secs << "s" << endl;
00306 
00307    }
00308 #endif /* VERBOSE_INFO */
00309  }
00310 
00311 
00312  void display_StatusLegend(void)
00313  {
00314 #ifdef VERBOSE_INFO
00315    cout_status << "Legend of the status information:" << endl;
00316    cout_status << "#static relations{distribution}/#static factorbase," << endl
00317                << "#directly sieved dynamic factors (single large primes)/#dynamic-FB," << endl;
00318  #ifdef IS_CLIENT
00319    cout_status << "#special factors (double large primes) ->{distribution}" << endl;
00320  #else
00321    cout_status << "#special factors (double large primes)" << endl;
00322  #endif
00323  #ifndef USE_NETWORK
00324    // sieve offset is only useful for standalone-version
00325    cout_status << " [sievepos]" << endl;
00326  #endif
00327    cout_status << " -> % progress" << endl;
00328 #endif
00329 
00330    if (!StartTimestamp)
00331     {
00332      StartTimestamp=time(NULL); StartFilling=StaticRelations::Count(); // initialize these for calculating ETA and other stats
00333      PreviousTimestamp=StartTimestamp; // memorize the point in time
00334      for (int i=0; i<samples; ++i)
00335       {
00336         sample[i].Zeitpunkt=StartTimestamp;
00337         sample[i].Filling=StaticRelations::Count();
00338         sample[i].total_sieved=relations_sieved_so_far;
00339       }
00340     }
00341  }
00342 
00343  bool StatusReport(const bool force_now = false)
00344  {
00345    /*
00346       output a status message, if at least 15 seconds have passed since the
00347       previous status message.
00348       return true, if any output was issued. (false if output was skipped.)
00349     */ 
00350 
00351    if (!force_now && difftime(time(NULL),PreviousTimestamp)<15.0) return false;
00352    // we want to output a status message now
00353    
00354    ProgressStats.take_sample();
00355 
00356    const time_t now=time(NULL);
00357 
00358 #ifdef VERBOSE_NOTICE
00359    {
00360      // print estimated time of arrival
00361      char buf[32]; struct tm my_tm;
00362      localtime_r(&now,&my_tm); asctime_r(&my_tm,buf);
00363      buf[24]='\0'; // get rid of trailing newline
00364      cout_status << buf << ": ";
00365    }
00366 #endif
00367 
00368 #ifdef VERBOSE_INFO
00369    cout_status << "Status for " << n << endl;
00370 
00371  #ifdef IS_SERVER
00372    {
00373     // print a sheet with all clients that ever have connected to this server
00374     AllClientStats_Mutex.lock();
00375     for (TAllClientStats::const_iterator pos=AllClientStats.begin(); pos!=AllClientStats.end(); ++pos)
00376       cout_status << (pos->first+"                    ").substr(0,20) << ":" << pos->second.info() << endl;
00377     AllClientStats_Mutex.unlock();
00378    }
00379  #endif
00380 #endif /* VERBOSE_INFO */
00381 
00382 #ifdef VERBOSE_NOTICE
00383    // overall statistics
00384    cout_status << StaticRelations::Count()
00385         << "{"
00386         << DynamicFactorRating.entry(0);
00387 
00388    for(int i=1; i<DynamicFactorRating.size(); ++i)
00389     cout_status << "," << DynamicFactorRating.entry(i);
00390 
00391    cout_status << "}/" << StaticFactorbase::Size() << ","
00392         << directly_sieved_DynamicFactors << "/"
00393         << DynamicFactorRelations.size();
00394 
00395  #ifdef IS_SERVER
00396    cout_status << "{active:" << DynamicFactorRelations.size_active()
00397       << ",passive:" << DynamicFactorRelations.size_passive()
00398       << "}";
00399  #endif
00400 
00401    cout_status << ",";
00402  #ifdef IS_CLIENT
00403    cout_status << directly_sieved_SpecialFactors;
00404  #else
00405    cout_status
00406         << SpecialRelations::Count()
00407            // BUG/remark: SpecialFactorRelations is not protected by a
00408            // mutex, we actually can get wrong results, if we read
00409            // SpecialFactorRelations.size() while another thread is
00410            // modifying the set. But since we do read-only access, this
00411            // should not cause any harm. (this actually happened once while
00412            // Zyklensuche was active)
00413         << "->{" << Special_to_dynamic_Factor_hit << "/" << Special_hit
00414         << "/" << DLP_cycle_hits << "}";
00415  #endif
00416  #ifndef USE_NETWORK
00417    // Sieve offset only useful for standalone version
00418    cout_status << " [" << SieveOffset << "]";
00419  #endif
00420    cout_status.setf(ios::left, ios::adjustfield);
00421    cout_status << " -> ca. " << setw(5) << setprecision(4)
00422         << 100.0*StaticRelations::Count()/StaticFactorbase::Size()
00423         << "%" << endl;
00424 #ifdef VERBOSE_INFO
00425    cout_status << "mpqs interval ";
00426    Polynom.save(cout_status); // output mpqs polynomial data
00427 #endif
00428 
00429 #endif /* VERBOSE_NOTICE */
00430 
00431    PreviousTimestamp=now; // memorize timestamp
00432  #ifndef IS_CLIENT
00433    calc_ETA();
00434  #endif
00435 
00436    // only update ringbuffer, if
00437    // at least 1 minute has passed and the filling has increased.
00438    if (now-sample[i_newest_sample].Zeitpunkt>=60 && StaticRelations::Count()>sample[i_newest_sample].Filling)
00439     {
00440       const int i_oldest_sample=(i_newest_sample+1)%samples;
00441       i_newest_sample=i_oldest_sample; // because of ringbuffer!
00442       sample[i_newest_sample].Zeitpunkt=now;
00443       sample[i_newest_sample].Filling=StaticRelations::Count();
00444       sample[i_newest_sample].total_sieved=relations_sieved_so_far;
00445     }
00446 
00447 #ifdef VERBOSE_NOTICE
00448 #ifndef IS_SERVER
00449    // this info is only relevant to clients (and standalone version)...
00450    {
00451      // calculate and print DLP/minute performance
00452       const int i_oldest_sample=(i_newest_sample+1)%samples;
00453       const double t=difftime(now,sample[i_oldest_sample].Zeitpunkt);
00454       const double sieved_relations_per_sec = (relations_sieved_so_far-sample[i_oldest_sample].total_sieved)/t;
00455       cout << "sieved relations: " << relations_sieved_so_far
00456            << " [" << sieved_relations_per_sec*60.0 << " per minute]"
00457            << " #DYNFB: " << DynamicFactorArrays::DynamicFactorsInUse << ", countdown now: " << DynamicFactorArrays::DYNFB_threshold
00458            << endl;
00459  #if 0 || defined(VERBOSE)
00460       cout_status << "oldest sample: " << sample[i_oldest_sample].Zeitpunkt << ": " << sample[i_oldest_sample].Filling << endl;
00461       cout_status << "newest sample: " << sample[i_newest_sample].Zeitpunkt << ": " << sample[i_newest_sample].Filling << endl;
00462  #endif
00463    }
00464 #endif
00465 #endif /* VERBOSE_NOTICE */
00466 
00467    return true;
00468  }
00469 
00470 
00471 #ifndef IS_CLIENT
00472  void XML_StatusReport(ostream &os)
00473  {
00474    {
00475      time_t t = time(NULL);
00476      char buf [32];
00477      ctime_r(&t,buf); // get localtime
00478      buf[24]='\0'; // get rid of trailing newline
00479      char* const datestr = &buf[4]; // be less verbose
00480      os << "<QSIEVESTATISTICS TIME=\"" << datestr
00481         << "\" VERSION=\"" << VERSION << "\" >" << endl;
00482    }
00483 
00484    os << "<NUMBERSECTION>" << endl;
00485    if (FoundFactors.regarding!="") os << "<ITEM CONTENT=\"input: \">" << FoundFactors.regarding << "</ITEM>" << endl;
00486    if (mpz_cmp_ui(n,1)!=0) os << "<ITEM CONTENT=\"remaining: \">" << n << "</ITEM>" << endl;
00487    os << "</NUMBERSECTION>" << endl;
00488 
00489    if (!FoundFactors.empty())
00490     {
00491 // FIXME! TFoundFactors needs to be wrapped (not threadsafe!)
00492       os << "<TABLE CONTENT=\"FACTORS\" >";
00493        for (TFoundFactors::const_iterator pos=FoundFactors.begin(); pos!=FoundFactors.end(); ++pos)
00494         os << "<FACTOR>" << (*pos) << "</FACTOR>";
00495       os << "</TABLE>" << endl;
00496     }
00497 
00498    if (ecm_curves_processed)
00499     {
00500       os << "<TABLE CONTENT=\"Elliptic Curves\" >"
00501          << "<tr><td>ecm status</td><td>" << ecm_curves_processed << " / " << elcu_Kurven << "</td></tr>" << endl
00502          << "<tr><td>Phase 1</td><td>" << elcu_Phase1 << "</td></tr>" << endl
00503          << "<tr><td>Phase 2</td><td>" << elcu_Phase2 << "</td></tr>" << endl
00504          << "</TABLE>" << endl;
00505     }
00506 
00507    ProgressStats.XML(os); // a table with progress statistics
00508  #ifdef IS_SERVER
00509    {
00510     // print a sheet with all clients that ever have connected to this server
00511     AllClientStats_Mutex.lock();
00512     if (!AllClientStats.empty())
00513      {
00514        os << "<TABLE CONTENT=\"NETCLIENTS\" >" << endl;
00515        for (TAllClientStats::const_iterator pos=AllClientStats.begin(); pos!=AllClientStats.end(); ++pos)
00516         os << "<NETCLIENT "
00517            << " HOSTNAME=\"" << pos->first << "\""
00518            << pos->second.XML_info()
00519            << " />" << endl;
00520        os << "</TABLE>" << endl;
00521      }
00522     AllClientStats_Mutex.unlock();
00523    }
00524  #endif
00525 
00526    // overall statistics
00527    os << "<STATUSINFO>" << endl;
00528    os << "<RELFOUND>" << StaticRelations::Count()
00529       << "<RELDISTRIBUTION>"
00530       << DynamicFactorRating.entry(0);
00531 
00532    for(int i=1; i<DynamicFactorRating.size(); ++i)
00533     os << "," << DynamicFactorRating.entry(i);
00534 
00535    os << " </RELDISTRIBUTION>"
00536       << "</RELFOUND>" << endl
00537       << "<RELTOTAL>" << StaticFactorbase::Size() << "</RELTOTAL>" << endl
00538       << "<SLPFOUND>" << directly_sieved_DynamicFactors << "</SLPFOUND>"
00539       << "<SLPTOTAL>" << DynamicFactorRelations.size();
00540 
00541  #ifdef IS_SERVER
00542    os << "<RELDISTRIBUTION>" << "active:" << DynamicFactorRelations.size_active()
00543       << ", passive:" << DynamicFactorRelations.size_passive()
00544       << " </RELDISTRIBUTION>";
00545  #endif
00546 
00547    os << "</SLPTOTAL>";
00548 
00549  #ifndef IS_CLIENT
00550    os << "<DLPTOTAL>" << SpecialRelations::Count() << "</DLPTOTAL>" << endl;
00551            // BUG/remark: SpecialFactorRelations is not protected by a
00552            // mutex, we actually can get wrong results, if we read
00553            // SpecialFactorRelations.size() while another thread is
00554            // modifying the set. But since we do read-only access, this
00555            // should not cause any harm. (this actually happened once while
00556            // Zyklensuche was active)
00557 
00558    os << "<DLP2SLP>" << Special_to_dynamic_Factor_hit << "</DLP2SLP>"
00559       << "<DLP2STATIC>" << Special_hit << "</DLP2STATIC>"
00560       << "<DLP2CYCLE>" << DLP_cycle_hits << "</DLP2CYCLE>" << endl;
00561  #endif
00562 
00563    os.setf(ios::left, ios::adjustfield);
00564    os << "<PERCENTAGEDONE>" << setw(5) << setprecision(4)
00565         << 100.0*StaticRelations::Count()/StaticFactorbase::Size()
00566         << "%" << "</PERCENTAGEDONE>" << endl;
00567    os << "</STATUSINFO>" << endl;
00568    os << "</QSIEVESTATISTICS>" << endl;
00569  }
00570 #endif /* ndef IS_CLIENT */
00571 
00572 
00573 } // end of namespace statistical_data
00574 using statistical_data::StatusReport;
00575 using statistical_data::display_StatusLegend;

Generated on Wed Nov 7 23:29:25 2007 for Qsieve by  doxygen 1.5.4