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`:

$ 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)