home *** CD-ROM | disk | FTP | other *** search
/ ftp.cse.unsw.edu.au / 2014.06.ftp.cse.unsw.edu.au.tar / ftp.cse.unsw.edu.au / pub / doc / papers / misc / cs.toronto.edu:programming / c-news.tbl.ms < prev    next >
Encoding:
Text File  |  1992-10-18  |  35.0 KB  |  1,162 lines

  1. .\" tbl newspaper | troff -ms | dcat
  2. .\" tbl newspaper | nroff -ms | col
  3. .\" Formatting specs:  paragraph space, no header, page number in centered
  4. .\" footer, 6-inch text centered on 8.5 page, level-1 headers tight spacing.
  5. .SE PB 0.6
  6. .SE CH
  7. .SE CF %
  8. .SE FPH
  9. .SE LL 6i
  10. .SE PO 1.11i
  11. .HS 1 NUM L B 1 0 NOPAGE 5 4
  12. .\" Macro for footnote-marker planting.
  13. .de ZF
  14. .ie !'\\$2'*' \\$1\\s-2\\v'-0.1c'\\$2\\v'0.1c'\\s0\\$3
  15. .el \\$1\\s-2\\$2\\s0\\$3
  16. ..
  17. .TL
  18. .ft HB
  19. .ps 14
  20. News Need Not Be Slow
  21. .ps
  22. .ft
  23. .AU
  24. .ft I
  25. Geoff Collyer
  26. .ft
  27. .AI
  28. .\" Computing Services
  29. .ft I
  30. .ZF "Department of Statistics" \fR*\fI
  31. .\" Stupid macros won't allow a footnote here... moved it down.
  32. University of Toronto
  33. utzoo!utcsri!utfraser!geoff
  34. .ft
  35. .AU
  36. .ft I
  37. Henry Spencer
  38. .ft
  39. .AI
  40. .ft I
  41. Zoology Computer Systems
  42. University of Toronto
  43. utzoo!henry
  44. .ft
  45. .AB
  46. C news is a re-write,
  47. from scratch,
  48. of the `transport layer' of the Usenet software.
  49. C rnews runs at over 19 times the speed of B rnews;
  50. C expire runs in minutes rather than the hours taken by B expire.
  51. These performance improvements were (mostly) quite simple and
  52. straightforward, and they exemplify general principles of performance
  53. tuning.
  54. .AE
  55. .NH 1
  56. .ft HB
  57. History and Motivation
  58. .PP
  59. In the beginning (of Usenet) (1979) was A news,
  60. .FS
  61. * Work done mostly while at U of T Computing Services.
  62. .FE
  63. written at Duke University by
  64. Steve Bellovin,
  65. Stephen Daniel,
  66. Tom Truscott
  67. and others.
  68. A single program,
  69. .I news ,
  70. received, relayed, perused and cleaned out news articles.
  71. All articles were stored in a single
  72. .ZF \s-2UNIX\s0 \(dg
  73. .FS
  74. \(dg UNIX is a registered trademark of AT&T.
  75. .FE
  76. directory,
  77. which made A news suitable for local news and low volumes of network news.
  78. News articles were exchanged using a simple message format
  79. in which the first five lines of a message contained the information
  80. nowadays found in the article headers:
  81. unique article-id,
  82. newsgroup(s), author, subject,
  83. date posted.
  84. .PP
  85. As Usenet began to grow (1981),
  86. people in and around the University of California at Berkeley,
  87. including Matt Glickman and Mark Horton,
  88. modified A news extensively.
  89. The articles of each newsgroup were now stored in a separate
  90. directory.
  91. The message format was changed from the rigid and inextensible
  92. A news header format to one conforming to ARPA RFC 822
  93. (the current ARPA mail-message format standard).
  94. .I News
  95. was broken into separate programs:
  96. \fIreadnews\fR, \fIinews\fR (aka \fIrnews\fR), and \fIexpire\fR.
  97. The authors dubbed the result ``B news''.
  98. Since the release of B news,
  99. it has replaced A news
  100. .ZF almost \(dd
  101. everywhere on Usenet.
  102. .FS
  103. \(dd AT&T Bell Laboratories Research still runs A news for local newsgroups.
  104. .FE
  105. .PP
  106. It soon became clear that sending individual articles
  107. from machine to machine as separate
  108. .I uucp
  109. transactions was unacceptably slow,
  110. in part because it produced large
  111. .I uucp
  112. spool directories,
  113. which are searched quite
  114. .ZF slowly *
  115. by the kernel.
  116. .FS
  117. * Recent \fIuucp\fRs
  118. (notably Honey DanBer)
  119. provide spool sub-directories,
  120. and recent 4BSD
  121. (4.3BSD and later)
  122. kernels provide linear
  123. (as opposed to quadratic)
  124. directory searching,
  125. both of which help this problem.
  126. .FE
  127. Sites began to
  128. .I batch
  129. articles into batches of (typically) 50,000\-100,000 bytes
  130. for transmission to other machines.
  131. .PP
  132. At about this time,
  133. B news was changed to
  134. file news articles in a tree,
  135. as (for example) /usr/spool/news/net/women/only/123,
  136. rather than as /usr/spool/news/net.women.only/123.
  137. The motive for this was primarily elimination of problems with long
  138. newsgroup names, but shortening directories (and thus speeding searches)
  139. was also a consideration.
  140. .PP
  141. As Usenet traffic continued to grow explosively,
  142. sites began to use data compression on news batches.
  143. The main objective was to reduce expensive long-distance phone time,
  144. but again performance improved a bit:
  145. the extra processor time used for compression and decompression was more
  146. than gained back by the reduction in processor time used by
  147. .I uucp
  148. itself.
  149. .PP
  150. Unfortunately, B news has been modified by many people since 1981,
  151. and has mutated repeatedly to match the changing nature of Usenet.
  152. It has become complex, slow, and difficult to maintain.
  153. .PP
  154. During 1985, we observed that the nightly arrival
  155. of new news and expiry of old news were consuming resources
  156. far out of proportion to the volume of data
  157. .ZF involved \(dg .
  158. .FS
  159. \(dg Never mind the cost/benefit ratio.
  160. .FE
  161. .I Expire
  162. often ran for 90 minutes, and
  163. .I rnews
  164. processing averaged
  165. 10 seconds or more per article.
  166. Both programs tended to cripple systems by performing
  167. much disk i/o and eating much system-mode CPU time.
  168. .B Utcs
  169. was running B 2.10.1 news then and
  170. .B utzoo
  171. was running B 2.10 news.
  172. Although newer B news releases were available,
  173. they offered little beyond B 2.10, and it was often
  174. necessary to regression-test new B news releases to
  175. verify that reported, published bug fixes had in fact been applied.
  176. .PP
  177. Spencer acted first and rewrote
  178. .I expire
  179. from the ground up.
  180. Though it initially lacked any form of selective expiry,
  181. this
  182. .I expire ,
  183. when run each night,
  184. finished in about 15 minutes.
  185. (This was on
  186. 750-class machines
  187. holding all Usenet news and expiring after 14 days.)
  188. .PP
  189. Collyer observed in November 1985 that B
  190. .I rnews ,
  191. upon receiving a batch of news,
  192. immediately \fIexec\fRed a trivial unbatcher which copied each article
  193. into a temporary file and then forked and \fIexec\fRed B rnews again.
  194. Such a technique is clearly overkill for articles
  195. averaging about 3,000 bytes each.
  196. Preliminary experiments failed to produce a modified B rnews
  197. that could unravel a batch without forking.
  198. Consultation with Rick Adams,
  199. the current B-news maintainer,
  200. revealed that this same technique remained
  201. in the upcoming B news release (variously B 2.10.3 or B 2.11).
  202. Within one
  203. .ZF week \(dd ,
  204. .FS
  205. \(dd 40 hours, Collyer didn't have to work hard.
  206. .FE
  207. a from-scratch C
  208. .I rnews
  209. prototype was working well enough
  210. to run experimentally on a `leaf' machine receiving a subset of news.
  211. .PP
  212. This prototype version lacked a good many necessary amenities,
  213. and over the next eight months it was enhanced to bring it up to full
  214. functionality.
  215. It was also tuned heavily to improve its performance, since it was faster
  216. than B
  217. .I rnews
  218. but still not fast enough to make us happy.
  219. .PP            
  220. Once the
  221. .I rnews
  222. newsgroup name matching routines were working,
  223. Spencer revised
  224. .I expire
  225. to add selective expiry,
  226. specified in a control file.
  227. Recently, we have also revised our old
  228. batcher
  229. heavily,
  230. largely to add capability
  231. but with an eye on performance.
  232. .NH 1
  233. .ft HB
  234. Rnews Performance
  235. .PP
  236. The basic objective of C news was simpler code and higher performance.
  237. This may sound trite, but note that performance was an explicit objective.
  238. That was important.
  239. \fIPrograms will seldom run faster unless you care about making them
  240. run faster.\fR
  241. .PP
  242. `Faster' implies comparison to a slower version.
  243. Knowing the value of improvements, and assessing this in relation to their
  244. cost, requires knowing the performance of the unimproved version.
  245. Collyer kept detailed records of his work on
  246. .I rnews ,
  247. so he could see how much progress he was making.
  248. See the Appendix for the final result.
  249. \fITo know how to get somewhere,
  250. you must know where you are starting from.\fR
  251. .PP
  252. The first functional C
  253. .I rnews
  254. ran at about 3 times the speed of B
  255. .I rnews .
  256. We had assumed that merely eliminating the fork/exec on each
  257. article would give a factor of 10 improvement,
  258. so this was disappointing.
  259. \fIAvoiding obvious performance disasters helps...
  260. but it's not always enough.\fR
  261. .PP
  262. Profiling, first with
  263. .I prof (1)
  264. and later with 4.2BSD's
  265. .I gprof (1),
  266. and rewriting of the bottlenecks thus discovered,
  267. eventually brought the speed up
  268. to over 19 times the speed of B
  269. .I rnews .
  270. This required a number of write-profile-study-rewrite cycles.
  271. There is undoubtedly still a lot of code
  272. which could be faster than it is,
  273. but since profiling shows that
  274. it doesn't have a significant impact on overall performance,
  275. who cares?
  276. \fITo locate performance problems, look through the eyes of thy profiler.\fR
  277. .PP
  278. Collyer first experimented with using
  279. .I read
  280. and
  281. .I write
  282. system calls instead of
  283. .I fread
  284. and
  285. .I fwrite ,
  286. and got a substantial saving.
  287. Though the usage of system calls in this experiment was unportable,
  288. the saving eventually lead him to rewrite
  289. .I fread
  290. and
  291. .I fwrite
  292. from scratch
  293. to reduce the per-byte overheads.
  294. This helped noticeably, since pre-System-V
  295. .I fread
  296. and
  297. .I fwrite
  298. are really quite inefficient.
  299. \fIIf thy library function offends thee, pluck it out and fix it.\fR
  300. .PP
  301. At the time, C
  302. .I rnews
  303. was doing fairly fine-grain locking,
  304. essentially locking each file independently on each use.
  305. News doesn't need the resulting potential concurrency,
  306. especially when
  307. .I rnews
  308. runs relatively quickly,
  309. and the locking was clearly
  310. a substantial fraction of the execution time.
  311. C
  312. .I rnews
  313. was changed to use B-news compatible locking,
  314. with a single lock for the news system as a whole.
  315. \fISimplicity and speed often go together.\fR
  316. .PP
  317. When sending articles to a site using batching,
  318. .I rnews
  319. just appends the filename of each article to a \fIbatch file\fR for that site.
  320. The batch file is later
  321. processed by the batcher.
  322. In principle, batching is an option, and different sites may get different
  323. sets of newsgroups.
  324. In practice, few articles are ever sent unbatched, and most articles go to
  325. all sites fed by a given system.
  326. This means that
  327. .I rnews
  328. is repeatedly appending lines to the same set of batch files.
  329. \%Noticing this, Collyer changed C
  330. .I rnews
  331. to keep these files open, rather than re-opening them for every
  332. .ZF article * .
  333. .FS
  334. * The price for this tactic is that the code has to be prepared for the
  335. possibility that
  336. the number of sites being fed exceeds the supply of file descriptors.
  337. Fortunately, that is rare.
  338. .FE
  339. \fIOnce you've got it, hang onto it.\fR
  340. .PP
  341. These two simple changes\(emcoarser locking and retaining open files\(emcut
  342. system time by about 20% and real time by still more.
  343. .PP
  344. On return from Christmas holidays,
  345. after considerable agonizing over performance issues,
  346. Collyer turned
  347. some small, heavily-used character-handling functions into macros.
  348. This reduced user-mode time quite a bit.
  349. \fIA function call is an expensive way to perform a small, quick task.\fR
  350. .PP
  351. .I Rnews
  352. was always looking up files by full pathnames.
  353. Changing it to
  354. .I chdir
  355. to the right place and use relative names thereafter reduced system time
  356. substantially.
  357. \fIAbsolute pathnames are convenient but not cheap.\fR
  358. .PP
  359. Studying the profiling data revealed that
  360. .I rnews
  361. was spending a lot of time re-re-re-reading the
  362. .I sys
  363. and
  364. .I active
  365. files.
  366. These files are needed for processing every article, and
  367. they are not large.
  368. Collyer modified
  369. .I rnews
  370. to simply read these files in once and keep them in core.
  371. This change alone cut system time and real time by roughly 30%.
  372. \fIAgain, once you've got it, don't throw it away!\fR
  373. .PP
  374. There is a more subtle point here, as well.
  375. When these files were re-read every time, they were generally processed a
  376. line at a time.
  377. The revised strategy was to
  378. \fIstat\fR the file to determine its size,
  379. \fImalloc\fR enough space for the whole file,
  380. and bring it in with a single \fIread\fR.
  381. This is a vastly more efficient way to read a file!
  382. \fITasks which can be done in one operation should be.\fR
  383. .PP
  384. At this point
  385. (mid-January 1986),
  386. C
  387. .I rnews
  388. was faster than B
  389. .I rnews
  390. by one order of magnitude,
  391. and there was much rejoicing.
  392. .PP
  393. In principle, the `Newsgroups:' header line, determining what
  394. directories the article will be filed in, can be arbitrarily far from
  395. the start of the article.
  396. In practice, it is almost always found within the first thousand
  397. bytes or so.
  398. By complicating rnews
  399. substantially,
  400. it became possible in most cases to
  401. .I creat
  402. the file in the right place (or the first of the right places) in
  403. .I /usr/spool/news
  404. before writing any of the article to disk,
  405. eliminating the need for temporary files or even
  406. temporary links.
  407. The improvement in system time was noticeable, and the improvement in user
  408. time was even more noticeable.
  409. \fIPrepare for the worst case, but optimize for the typical case.\fR
  410. .PP
  411. There are certain circumstances, notably control-message articles, in which
  412. it is necessary to re-read the article after filing it.
  413. .I Rnews
  414. originally re-opened the article to permit this.
  415. Changing the invocation of
  416. .I fopen
  417. to use the \fBw+\fR mode made it possible to just
  418. seek back to the beginning instead, which is
  419. .I much
  420. faster.
  421. This, plus some similar elimination of other redundant
  422. calls to
  423. .I open ,
  424. reduced system time by over 30%.
  425. \fIGet as much mileage as possible out of each call to the kernel.\fR
  426. .PP
  427. Both scanning the in-core
  428. .I active
  429. and
  430. .I sys
  431. files and re-writing the
  432. .I active
  433. file are simpler if the in-core copies are kept exactly as on disk,
  434. but this implied
  435. frequent scans to locate the ends of lines.
  436. It turned out to be worthwhile to pre-scan the
  437. .I active
  438. file for line boundaries, and remember them.
  439. \fIWhen storing files in an unstructured way,
  440. a little remembered information about
  441. their structure goes a long way in speeding up access.\fR
  442. .PP
  443. We already had a
  444. .I STREQ
  445. macro, just a simple invocation of
  446. .I strcmp ,
  447. as a convenience.
  448. As a result of some other experience by Spencer,
  449. Collyer tried replacing some calls of
  450. .I strncmp
  451. by a
  452. .I STREQN
  453. macro, which compared the first character of the two strings in-line
  454. before incurring the overhead of calling
  455. .I strncmp .
  456. This sped things up noticeably,
  457. and later got propagated through more and more
  458. of the code.
  459. String-equality tests usually fail on the very first character.
  460. \fITest the water before taking the plunge.\fR
  461. .PP
  462. While looking at string functions, Collyer noticed
  463. that
  464. .I strncmp s
  465. to determine whether a line was a particular header line
  466. had the comparison length
  467. computed by applying
  468. .I strlen
  469. to the prototype header.
  470. With a little bit of work, the prototypes were isolated as individual
  471. character arrays initialized at compile time.
  472. This permitted substituting the compile-time
  473. .I sizeof
  474. operation for the run-time
  475. .I strlen .
  476. \fILet the compiler do the work when possible.\fR
  477. .PP
  478. At this point, profiling was turned off temporarily for speed tests.
  479. Profiling does impose some overhead.
  480. The speed trials showed that C
  481. .I rnews
  482. was now running at over 15 times the speed of B
  483. .I rnews .
  484. .PP
  485. After months of adding frills, bunting and B 2.11
  486. .ZF compatibility * ,
  487. .FS
  488. * And supposed B 2.11 compatibility, as those who remember the
  489. short-lived cross-posting restrictions will recall.
  490. .FE
  491. Collyer again returned to performance tuning in August 1986.
  492. The 4.2BSD kernel on
  493. .B utcs
  494. now included the 4.3BSD \fInamei\fR caches,
  495. which improve filename-lookup performance considerably.
  496. Unfortunately, considerations of crash recovery dictated some loss in
  497. performance:
  498. it seemed desirable to put batch-file additions out by the line rather
  499. than by the block.
  500. \fIPerformance is not everything.\fR
  501. .PP
  502. .I Gprof
  503. revealed that newsgroup name matching
  504. was an unexpected bottleneck,
  505. so that module was extensively tweaked
  506. by adding
  507. .B register
  508. declarations, turning functions into macros,
  509. applying
  510. .I STREQN
  511. and such more widely,
  512. and
  513. generally tuning the details of string operations.
  514. The code that handled
  515. .I sys -file
  516. lines got similar treatment next.
  517. The combination cut 40% off user-mode time.
  518. \fIPersistent tuning of key modules can yield large benefits.\fR
  519. .PP
  520. Newsgroup matching remained moderately costly, and an investigation of
  521. where it was being used revealed two separate tests for a particular
  522. special form of name.
  523. It proved awkward to combine the two, so the testing routine was changed
  524. to remember having done that particular test already.
  525. \fIIf the same question is asked repeatedly, memorize the answer.\fR
  526. .PP
  527. By this time, the number of system calls needed to process a single article
  528. could be counted on one's fingers,
  529. and their individual contributions could be assessed.
  530. At one point it was desirable for a
  531. .I creat
  532. to fail if the file already existed, so this was being checked with a call to
  533. .I access
  534. first.
  535. John Gilmore pointed out that on
  536. systems with a 3-argument
  537. .I open
  538. (4.2BSD, System V),
  539. this test can be folded into the
  540. .I open .
  541. The elimination of the extra name\(->file (\fInamei\fR) mapping
  542. cut both system time and real time by another 15%.
  543. (Note that this system \fIdoes\fR have \fInamei\fR cacheing!)
  544. \fIFile name lookups are expensive; minimize them.\fR
  545. .PP
  546. The development system
  547. (\fButcs\fP, a 750)
  548. is now filing 2-3 articles per second on average;
  549. .B utfraser
  550. (a Sun 3/160 with an Eagle disk)
  551. is typically filing 6-7 articles per second.
  552. C
  553. .I rnews
  554. runs over 19 times as fast in real time as B
  555. .I rnews ,
  556. over 25 times as fast in system-mode CPU time,
  557. roughly 3.6 times as fast in user-mode CPU time,
  558. and over 10 times as fast in combined CPU times.
  559. .PP
  560. With one exception (see \fIFuture Directions\fR),
  561. it now appears that very little can be done to speed up
  562. .I rnews
  563. without changing the specifications.
  564. It seems to be executing nearly the bare minimum of system calls,
  565. and the user-level code has been hand-optimised fairly heavily.
  566. .NH 1
  567. .ft HB
  568. Expire Performance
  569. .PP
  570. The rewrite of
  571. .I expire
  572. that started this whole effort was
  573. only partly motivated by performance problems.
  574. Performance was definitely bad enough to require attention,
  575. but the B
  576. .I expire
  577. of the time also had some serious bugs.
  578. Worse, the code was a terrible mess and was almost impossible to understand,
  579. never mind fix.
  580. Early efforts were directed mainly at producing a version that would
  581. \fIwork\fR;
  582. rewriting
  583. .I expire
  584. from scratch simply looked like the easiest route.
  585. Decisions made along the way,
  586. largely for other reasons,
  587. nevertheless produced major speedups.
  588. .PP
  589. The first of these decisions was a reduction in the scope of the program.
  590. B
  591. .I expire
  592. had several options for doing quite unrelated tasks, such as
  593. rebuilding news's history file.
  594. The code for these functions was substantial and was somewhat interwoven
  595. with the rest.
  596. C
  597. .I expire
  598. adheres closely to a central tenet of the `Unix Philosophy':
  599. \fIa program should do one task, and do it well\fR.
  600. This may appear unrelated to performance, but better-focussed
  601. programs are generally simpler and smaller, reducing their resource
  602. consumption and making performance tuning easier (and hence more likely).
  603. In addition, a multipurpose program almost always pays some performance
  604. penalty for its generality.
  605. .PP
  606. The second significant decision had the biggest effect on performance,
  607. despite being made for totally unrelated reasons.
  608. For each news article,
  609. the B news history file contained the arrival date and an indication
  610. of what newsgroups it was in.
  611. This is \fIalmost\fR all the information that \fIexpire\fR needs to decide
  612. whether to expire an article or not.
  613. The
  614. .ZF missing *
  615. data is whether the article contains an explicit expiry date,
  616. .FS
  617. * Recent versions of B news have made some attempt to redress this
  618. lack, but haven't gone as far as C expire.
  619. The discussion here applies to the B expire that was current at the time
  620. C expire was written.
  621. .FE
  622. and if so, what it is.
  623. B
  624. .I expire
  625. had to discover this for itself, which required opening the article
  626. and parsing its headers.
  627. A site which retains news for two weeks will have upwards of 5,000 articles
  628. on file.
  629. A few dozen of them will have explicit expiry dates.
  630. \fIBut B expire opened and scanned all 5,000+ articles every time it ran!\fR
  631. This was a performance disaster.
  632. .PP
  633. We actually did not want to parse headers in \fIexpire\fR at all,
  634. because the B news header-parsing code was (and is) complex and was known to
  635. contain major bugs.
  636. The performance implications of this were obvious,
  637. although secondary at the time.
  638. Header parsing is itself a non-trivial task, and accessing 5,000+ files
  639. simply cannot be made cheap.
  640. \fIInformation needed centrally should be kept centrally.\fR
  641. .PP
  642. The C news history file has the same format as that of B news, with one
  643. addition:
  644. a field recording the explicit expiry date, if any, of each article.
  645. If no expiry date is present in the article, the field contains `\-' as
  646. a
  647. .ZF placemarker \(dg .
  648. .FS
  649. \(dg It would be possible to simply compute a definitive expiry date for an
  650. article when it arrives, and record that.
  651. This would eliminate the decision-making overhead in \fIexpire\fR, but would
  652. greatly slow the response to changes in expiry policy.
  653. Since one reason to change policy is time-critical problems like a shortage
  654. of disk space, this loss of flexibility was judged unacceptable.
  655. It is better to leave the expiry decision to \fIexpire\fR and concentrate
  656. on making \fIexpire\fR do it quickly.
  657. .FE
  658. In this way, the header parsing is done \fIonce\fR per article, on arrival.
  659. In fact, the extra effort involved is essentially nil, since \fIrnews\fR
  660. does full header parsing at arrival time anyway.
  661. \fIRnews\fR had to be changed to write out the expiry date, and code
  662. which knew the format of the history file had to be changed to know about
  663. the extra field.
  664. Perhaps a dozen lines of code outside \fIexpire\fR were involved.
  665. .PP
  666. A crude first version of C
  667. .I expire ,
  668. incorporating these decisions in the
  669. most minimal way, ran an order of magnitude faster than B
  670. .I expire .
  671. Precise timing comparisons were not practical at the time, since the
  672. original motive for C
  673. .I expire
  674. was that B
  675. .I expire
  676. had stopped working completely,
  677. crippled by bugs in its header parsing.
  678. Later versions of B
  679. .I expire
  680. did cure this problem,
  681. but we were no longer interested in putting up slow, buggy software just to
  682. make an accurate comparison.
  683. .PP
  684. Further work on C
  685. .I expire
  686. mostly concentrated on cleaning up the hasty first
  687. version, and on incorporating desired features such as selective expiry by
  688. newsgroup.
  689. Selective expiry caused a small loss in performance by requiring
  690. \fIexpire\fR to check the newsgroup(s) of each article
  691. against an expiry-control list.
  692. Here, \fIexpire\fR benefitted from the work done to speed up
  693. the newsgroup-matching primitives of \fIrnews\fR,
  694. since \fIexpire\fR uses the same routines.
  695. \fIIf you re-invent the square wheel, you will not benefit when somebody
  696. else rounds off the
  697. .ZF corners \fR\(dd\fI .\fR
  698. .FS
  699. \(dd A corollary of this is:  \fIknow thy libraries, and use them\fR.
  700. .FE
  701. .PP
  702. One improvement that was made late in development was in the format of
  703. the dates stored in the history file.
  704. B
  705. .I rnews
  706. stored the arrival date in human-readable form,
  707. and \fIexpire\fR converted this into
  708. numeric form for comparisons of dates.
  709. Date conversion is a complex operation, and the widely-distributed
  710. \fIgetdate\fR function used by news is not fast.
  711. Inspection of the code established that \fIexpire\fR was the only
  712. program that ever looked at the dates in the history file.
  713. There is some potential use of the information for debugging,
  714. but this is infrequent, and a small program that converts decimal numeric
  715. dates to human-readable ones addresses the issue.
  716. Both C
  717. .I rnews
  718. and C
  719. .I expire
  720. now store the dates in decimal numeric form.
  721. \fIStore repeatedly-used information in a form that avoids expensive
  722. conversions.\fR
  723. .PP
  724. Actually, C
  725. .I expire
  726. bows to compatibility by accepting either form on
  727. input, but outputs only the decimal form as it regenerates the history file.
  728. Thus, in the worst case, \fIexpire\fR does the conversion only once for
  729. each history line, rather than once per line per run.
  730. \fI``If they hand you a lemon, make lemonade''.\fR
  731. .PP
  732. If \fIexpire\fR is archiving expired articles, it may need to create
  733. directories to hold them.
  734. This is an inherently expensive operation, but it is infrequently needed.
  735. However, checking to see whether it \fIis\fR in fact needed is also
  736. somewhat expensive... and the answer is almost always `no'.
  737. The same is true of checking to see whether the original article really
  738. still exists:  it almost always does.
  739. (This cannot be subsumed under generic `archiving failed' error handling
  740. because a missing original is just an article that was cancelled,
  741. and does not call for a trouble report.)
  742. Accordingly, C
  743. .I expire
  744. just charges ahead and attempts to do the copying.
  745. Only if this fails does \fIexpire\fR analyze the situation in detail.
  746. \fICarrying a net in front of you
  747. in case you trip is usually wasted effort.\fR
  748. .PP
  749. Archiving expired articles often requires copying across filesystem
  750. boundaries, since it's not uncommon to give current news and archived news
  751. rather different treatment for space allocation and backups.
  752. Copying from one filesystem to another can involve major disk head movement
  753. if the two filesystems are on the same spindle.
  754. Since head movement is expensive, maximizing performance requires getting
  755. as much use as possible out of each
  756. .ZF movement * .
  757. .FS
  758. * As witness the progressive increase in filesystem block size that
  759. produced major performance improvements in successive versions of 4BSD.
  760. .FE
  761. \fIExpire\fR is not a large program, and even on a small machine it can
  762. spare the space for a large copying buffer.
  763. So it does its archiving copy operations using an 8KB buffer.
  764. \fIBuying in bulk is often cheaper.\fR
  765. Since 8KB accommodates most news articles in one gulp, there is little
  766. point in enlarging it further.
  767. \fIThe law of diminishing returns does apply to buying in bulk.\fR
  768. .PP
  769. Since
  770. .I expire
  771. is operating on the
  772. history
  773. file at (potentially) the same time that
  774. .I rnews
  775. is adding more articles to it,
  776. some form of locking is necessary.
  777. Given that
  778. .I expire
  779. has to look over the whole database of news,
  780. and typically has to expire a modest fraction of the articles,
  781. it is a relatively long-running process compared to
  782. .I rnews .
  783. Contention for the history-file lock can be minimized by noting
  784. that
  785. .I rnews
  786. never does anything other than append to the file.
  787. So
  788. .I expire
  789. can leave the file unlocked while scanning it;
  790. the contents will not change.
  791. When
  792. (and only when)
  793. .I expire
  794. reaches end-of-file,
  795. it locks the news system, checks for and handles any further
  796. entries arriving on the end of the history file meanwhile,
  797. and finishes up.
  798. \fILocking data that won't change is wasteful.\fR
  799. .PP
  800. After careful application of these various improvements,
  801. C
  802. .I expire
  803. is fast enough that further speedup is not worth much effort.
  804. However, an analysis of where it spends its time does suggest one area
  805. that might merit attention in the future.
  806. \fIExpire\fR rebuilds the history file to reflect the removal of expired
  807. articles.
  808. The history file is large.
  809. \fIExpire\fR must also rebuild the \fIdbm\fR
  810. indexing data base, since it contains offsets into the history file.
  811. This data base is comparable in size to the history file itself, and is
  812. generated in a less orderly manner that requires more disk accesses.
  813. .PP
  814. Much of the time needed for these operations could be eliminated if
  815. \fIexpire\fR could mark a history line as `expired' without changing its
  816. size.
  817. This could be done by writing into the history file rather than by
  818. rebuilding the whole file, and the indexing database would not need
  819. alteration.
  820. This would also permit retaining information about an article after the
  821. article itself expires, which would simplify rejecting articles that arrive
  822. again (due to loops in the network, etc.) after the original has expired.
  823. The history file should still be cleaned out, and the indexing
  824. database rebuilt, occasionally.
  825. C
  826. .I expire
  827. contains some preliminary `hooks' for this approach, but to date
  828. full implementation does not seem justified:  C
  829. .I expire
  830. is already fast enough.
  831. \fIKnow when you are finished.\fR
  832. .NH 1
  833. .ft HB
  834. Batcher Performance
  835. .PP
  836. The C batcher is descended from a very old version written to add some
  837. minor functionality that was not present in the B batcher of the time.
  838. It is small and straightforward, and contains only a couple of noteworthy
  839. performance hacks.
  840. .PP
  841. The batcher works from a list of filed articles, to be composed into batches.
  842. The list is by absolute pathname.
  843. All of these files reside in the same area of the system's directory tree,
  844. and referring to them with absolute pathnames every time implies repeatedly
  845. traversing the same initial pathname prefix.
  846. To avoid this, the batcher initially \fIchdir\fRs to a likely-looking place
  847. such as \fI/usr/spool/news\fR.
  848. Thereafter, before using an absolute pathname to open an article, it checks
  849. whether the beginning of the pathname is identical to the directory where
  850. it already resides.
  851. If so, it strips this prefix off the name before proceeding.
  852. \fIIf you walk the same road repeatedly, consider moving to the other end.\fR
  853. .PP
  854. The batcher's input is usually in fairly random order, with little tendency
  855. for successive files to be in the same directory.
  856. If this were not the case, it would be worthwhile for the batcher to
  857. actually move around in the directory tree to be closer to the next file.
  858. .PP
  859. The batcher used to copy data
  860. using
  861. .I putc(getc())
  862. loops.
  863. This has been replaced by
  864. .I fread/fwrite
  865. which is significantly faster,
  866. especially if using the souped-up
  867. .I fread/fwrite
  868. mentioned earlier.
  869. \fIIf you need to move a mountain, use a bulldozer, not a teaspoon.\fR
  870. .NH 1
  871. .ft HB
  872. Future Directions
  873. .PP
  874. The one improvement we are still considering for
  875. .I rnews
  876. is a radical revision of the newsgroup-matching strategy.
  877. Newsgroup matching still consumes about 18% of user-mode processor time.
  878. The key observation is that the information that determines which newsgroups
  879. go to which sites seldom changes.
  880. It would probably be worth precompiling a bit array indexed by newsgroup
  881. and site, and recompiling it only when the
  882. .I active
  883. file or the
  884. .I sys
  885. file changes in a relevant way.
  886. This would cut the newsgroup-matching time to essentially zero.
  887. .PP
  888. .I Rnews
  889. would be faster
  890. (and simpler)
  891. if `Newsgroups:' and `Control:' were required
  892. to be the first two headers (if present) of each article.
  893. At present
  894. .I rnews
  895. tries to find them before starting to write the article out,
  896. so that it can put the article in the right place from the start,
  897. but it has to allow for the possibility that vast volumes of other
  898. headers may precede them.
  899. .PP
  900. Hashing
  901. .I active -file
  902. lookups in 
  903. .I rnews
  904. would be fun, but profiling suggests that it's not
  905. worthwhile unless the number of newsgroups is in the thousands.
  906. .PP
  907. When \s-2PDP-11\s+2's are truly dead on Usenet,
  908. the use of large per-process memories
  909. .I may
  910. allow further speedups to
  911. .I rnews
  912. by reading the entire batch into memory at once
  913. and writing each article to disk in a few
  914. .I writes
  915. (it can't easily be reduced to a single
  916. .I write
  917. because headers must be modified before filing).
  918. .PP
  919. One optimization we have \fInot\fR considered is re-coding key parts in
  920. assembler.
  921. C news already runs on five different types of machine.
  922. Use of assembler would be a maintenance nightmare, and probably would not
  923. yield benefits comparable to those of the more high-level changes.
  924. .NH 1
  925. .ft HB
  926. Acknowledgements
  927. .PP
  928. Ian Darwin ran the very earliest alpha versions of
  929. .I rnews
  930. and gave helpful feedback.
  931. Mike Ghesquiere, Dennis Ferguson and others
  932. have run later versions and prodded Collyer
  933. to fix or implement assorted things.
  934. John Gilmore and Laura Creighton read and criticized
  935. an early alpha version of
  936. .I rnews .
  937. .NH 1
  938. .ft HB
  939. Appendix:  rnews Times
  940. .PP
  941. Measurements have been taken on a VAX 750 running 4.2BSD
  942. under generally light load,
  943. using a batch of 297,054 bytes of net.unix-wizards
  944. containing 171 articles and ~104 cross-postings.
  945. All times are in seconds per article.
  946. .LP
  947. .TS
  948. c1 c1 c1 c1 c1
  949. c1 n1w(5n) n1w(5n) n1w(5n) l1w(3.5i) .
  950. time    real    user    sys    comments
  951. _
  952. 85 Dec  6 00:54    4.68    0.3    1.29    T{
  953. \fBB news\fP rejecting all.
  954. (b.1.rej)
  955. T}
  956. 85 Dec  6 00:54    3.184    0.69    0.67    T{
  957. first timing trial; \fIprofiling on\fP
  958. (c.1)
  959. T}
  960. 85 Dec  6 00:54    0.66    0.175    0.199    T{
  961. rejecting all
  962. (c.2.rej)
  963. T}
  964. 85 Dec  6 03:25    0.58    0.175    0.175    T{
  965. still rejecting all
  966. (c.3.rej)
  967. T}
  968. 85 Dec  6 23:46    9.058    0.631    2.251    T{
  969. \fBB news\fP using private directories,
  970. rejected 53 of the 171 articles as "too old"
  971. (b.2)
  972. T}
  973. 85 Dec  7 00:24    T{
  974. 2.0 (est)
  975. T}    -    -    T{
  976. on a 10 MHz 68000 with slow memory and slow disk
  977. (crude timings)
  978. (c.darwin.1)
  979. T}
  980. 85 Dec  7 00:40    7.576    0.684    2.403    T{
  981. \fBB news\fP without the "too old" reject code and having cleared out history
  982. (b.3)
  983. T}
  984. 85 Dec  7 04:43    1.99    0.49    0.53    T{
  985. accepting the articles, using read and write for bulk copies
  986. (c.4)
  987. T}
  988. 85 Dec  7 06:10    T{
  989. 2.261 (!)
  990. T}    0.497    0.449    T{
  991. optimized by less locking & keeping batch files open
  992. (c.5)
  993. T}
  994. 85 Dec  7 07:32    1.383    0.491    0.414    T{
  995. same as the last one, but with a lower load average (around 1.5)
  996. (c.6)
  997. T}
  998. 85 Dec 16 03:43    1.380    0.447    0.374    T{
  999. for calibration after misc. cleanup
  1000. (c.7, c.8)
  1001. T}
  1002. 86 Jan 13 00:23    1.232    0.349    0.301    T{
  1003. turned hostchar() into a macro
  1004. (c.9)
  1005. T}
  1006. 86 Jan 13 04:26    1.36    0.333    T{
  1007. 0.242 (!)
  1008. T}    T{
  1009. using in-core active file, under heavy load
  1010. (c.10)
  1011. T}
  1012. 86 Jan 13 08:24    1.94    0.349    0.253    T{
  1013. using in-core sys file too, under heavy load.
  1014. Re-run this trial!
  1015. (c.11)
  1016. T}
  1017. 86 Jan 13 08:42    T{
  1018. 0.892 (!)
  1019. T}    0.332    0.245    T{
  1020. re-run at better nice. Not striking, except for real time.
  1021. Was run in a large directory; ignore.
  1022. (c.12)
  1023. T}
  1024. 86 Jan 13 08:59    T{
  1025. 0.861 (!)
  1026. T}    0.333    T{
  1027. 0.212 (!)
  1028. T}    T{
  1029. re-run at good nice & in a small directory.
  1030. Have beaten B news by \fIone order of magnitude\fP on real & sys times!
  1031. Beat it by more than twice on user time.
  1032. (c.13)
  1033. T}
  1034. 86 Jan 21 19:15    1.208    0.349    0.245    T{
  1035. creat 1st link under final name,
  1036. only link to make cross-postings;
  1037. with HDRMEMSIZ too small
  1038. (c.14)
  1039. T}
  1040. 86 Jan 21 19:57    0.728    0.318    0.193    T{
  1041. previous mod, with HDRMEMSIZ of 4096
  1042. (c.15)
  1043. T}
  1044. 86 Jan 22 01:20    0.719    0.315    0.166    T{
  1045. fewer opens (just rewind the spool file), but Xref(s): not working
  1046. (c.16)
  1047. T}
  1048. 86 Jan 22 01:53    T{
  1049. 0.637 (!)
  1050. T}    0.314    T{
  1051. 0.154 (!)
  1052. T}    T{
  1053. fewer opens fixed to spell Xref: right; Xref: not working
  1054. (c.17)
  1055. T}
  1056. 86 Jan 22 04:00    0.874    0.325    0.174    T{
  1057. fewer opens with Xref: fixed (times may be high due to calendar)
  1058. (c.18)
  1059. T}
  1060. 86 Jan 22 05:45    0.694    0.309    0.159    T{
  1061. under lighter load, times are better
  1062. (c.19)
  1063. T}
  1064. 86 Jan 24 04:29    0.715    0.317    T{
  1065. 0.129 (!)
  1066. T}    T{
  1067. turn creat & open into just creat, under slightly heavy load
  1068. (c.20)
  1069. T}
  1070. 86 Jan 24 06:06    T{
  1071. 0.628 (!)
  1072. T}    T{
  1073. 0.288 (!)
  1074. T}    T{
  1075. 0.129 (!)
  1076. T}    T{
  1077. reduce number of calls on index
  1078. (by noting line starts at the start)
  1079. and strncmp (via macro)
  1080. in active.mem.c,
  1081. but still profiling and writing stdout and stderr to the tty
  1082. (c.21)
  1083. T}
  1084. 86 Jan 24 07:22    0.653    T{
  1085. 0.209 (!)
  1086. T}    T{
  1087. 0.123 (!)
  1088. T}    T{
  1089. fewer strlen calls
  1090. (by using \fBsizeof\fP s - 1),
  1091. writing stdout to /dev/null and with \fIprofiling off\fP,
  1092. but under moderate load; try again
  1093. (c.23)
  1094. T}
  1095. 86 Jan 24 07:35    T{
  1096. 0.574 (!)
  1097. T}    T{
  1098. 0.216 (!)
  1099. T}    T{
  1100. 0.123 (!)
  1101. T}    T{
  1102. as last time, but stdout to tty(!) and under light load.
  1103. \fIrunning 15.67 times as fast as B rnews\fP
  1104. (c.24)
  1105. T}
  1106. 86 Aug  8 04:23    0.839    0.51    0.124    T{
  1107. performance hit: fflush after each history line for crash-resilience;
  1108. run for \fIgprof\fP output and calibration with later runs.
  1109. running under 4.2.1BSD (has 4.3 namei cache) now.
  1110. real and user times are way up;
  1111. due to gprof profiling?
  1112. (c.25)
  1113. T}
  1114. 86 Aug  8 04:24    0.962    T{
  1115. 0.438 (!)
  1116. T}    0.131    T{
  1117. run with faster ngmatch,
  1118. with \fBregister\fP decl.s and wordmatch and STREQN macros;
  1119. saved 15% user.
  1120. User time is better than c.25, but still up from c.24.
  1121. (c.26)
  1122. T}
  1123. 86 Aug 10 07:35    0.805    T{
  1124. 0.345 (!)
  1125. T}    0.135    T{
  1126. further speedups: ngmatch has more \fBregister\fP decl.s and in-line index;
  1127. more use of STREQ(N) macro for str(n)cmp in hdrmatch,
  1128. ngmatch.c and transmit.c;
  1129. faster ishdr without index.
  1130. real & user times are better than both c.26 and c.25
  1131. (c.27)
  1132. T}
  1133. 86 Aug 11 04:19    1.012    T{
  1134. 0.303 (!)
  1135. T}    0.146    T{
  1136. rewrote sys.c, used INDEX and STREQ(N) macros throughout rnews.
  1137. real and sys times are up, but user continues to decline.
  1138. (c.28)
  1139. T}
  1140. 86 Aug 12 03:51    1.315    0.315    0.154    T{
  1141. minor tweaks: all.all.ctl caching, etc. (c.29)
  1142. T}
  1143. 86 Aug 30 17:56    0.564    T{
  1144. 0.189 (!)
  1145. T}    T{
  1146. 0.112 (!)
  1147. T}    T{
  1148. light load, thought we had 3-arg open in fileart, but didn't. Odd.
  1149. \fIStopped using gprof\fP.
  1150. (c.30)
  1151. T}
  1152. 86 Aug 30 17:57    T{
  1153. 0.475 (!)
  1154. T}    0.191    T{
  1155. 0.095 (!)
  1156. T}    T{
  1157. Really and truly use the 3-arg open.
  1158. \fI19 times B rnews speed.\fP
  1159. (c.31)
  1160. T}
  1161. .TE
  1162.