#+TITLE: txfib

Inspired by [[https://github.com/glenjamin/node-fib]]

*** Considered Approaches

Here's approaches presented in `txfib` for running a long CPU/memory intensive
operation:

- in separate threads (with a thread pool); e.g., `recfib()`
- in separate processes (without a process  pool); e.g., `binetfib_exact()`
- in a reactor thread
  + blocking the event-loop for a long time; e.g., `binetfib()`
  + non-blocking (cooperatively i.e., blocking for a short time);
    e.g., `iterfib()`, `sicpfib()`, `memfib()`

- iterfib :: O(n) steps, O(n) in memory (to hold the result)
             simple iterative non-blocking
- sicpfib :: O(log(n)) steps, O(n) in memory
             based on finding power of 2x2 matrix
- binetfib_exact :: O(1) *bigdecimal* steps, O(n) in memory in a process
                    Binet's formula; precision depends on n
- binetfib :: O(1) steps, O(1) memory in the reactor thread
              the same but with fixed precision
- memfib :: recursive formula with limited memoization running in the
            reactor thread cooperatively

- recfib ::  O(a**n) steps, O(a**n) memory in a thread
            recursive formula without memoization

nth fibonacci number has O(n) digits so each step is O(n) operation by
itself (except `binetfib()` that produces inexact results).

*** Usage

: $ pip install twisted
: $ twistd -ny fibonacci.py

Optionally you could install ~psutil~ to enable reporting CPU/memory
usage of the process.

Open [[http://localhost:1597/]] in browser

*** Performance

`/sicpfib/100` is ~2 times worse when node-fib on `ab`:

#+BEGIN_EXAMPLE
$ ab -n 10000 -c 50 'http://127.0.0.1:1597/sicpfib/100'
This is ApacheBench, Version 2.3 <$Revision: 655654 $>
Copyright 1996 Adam Twiss, Zeus Technology Ltd, http://www.zeustech.net/
Licensed to The Apache Software Foundation, http://www.apache.org/

Benchmarking 127.0.0.1 (be patient)


Server Software:        TwistedWeb/10.2.0
Server Hostname:        127.0.0.1
Server Port:            1597

Document Path:          /sicpfib/100
Document Length:        21 bytes

Concurrency Level:      50
Time taken for tests:   4.442 seconds
Complete requests:      10000
Failed requests:        0
Write errors:           0
Total transferred:      1290000 bytes
HTML transferred:       210000 bytes
Requests per second:    2251.45 [#/sec] (mean)
Time per request:       22.208 [ms] (mean)
Time per request:       0.444 [ms] (mean, across all concurrent requests)
Transfer rate:          283.63 [Kbytes/sec] received

Connection Times (ms)
              min  mean[+/-sd] median   max
Connect:        0    0   0.1      0       2
Processing:    18   22   1.4     22      34
Waiting:       18   22   1.4     22      34
Total:         19   22   1.5     22      34

Percentage of the requests served within a certain time (ms)
  50%     22
  66%     22
  75%     22
  80%     23
  90%     23
  95%     24
  98%     28
  99%     29
 100%     34 (longest request)
#+END_EXAMPLE