Easy Proof Omitted

A sink for random thoughts & experiments

0%

What is Planning?

Planning is the art and practice of thinking before acting. - Patrik Haslum

"Planning" is the name used in AI for computational problems that have to do with choosing a course of action. This may be for the purpose of creating a "plan", e.g., for a pair of robots to assemble a (simulated) IKEA table, for moving a sheet of paper through a printer, or exploiting IT security weaknesses. However, problems like model checking or computing genome edit distance are, in a computational sense, essentially the same.1

Planning Domain Description Language

PDDL was originally developed by Drew McDermott and the 1998 planning competition committee. It was inspired by the need to encourage the empirical comparison of planning systems and the exchange of planning benchmarks within the community. Its development improved the communication of research results and triggered an explosion in performance, expressivity and robustness of planning systems.

PDDL has become a de facto standard language for describing planning domains, not only for the competition but more widely, as it offers an opportunity to carry out empirical evaluation of planning systems on a growing collection of generally adopted standard benchmark domains. The emergence of a language standard will have an impact on the entire field, influencing what is seen as central and what peripheral in the development of planning systems.

  • Used by almost all implemented systems for deterministic planning
  • Supports a language comparable to what we have defined above (including schematic operators and quantification)
  • Syntax inspired by the Lisp programming language: e.g. prefix notation for formulae

Example: Rock Collecting Rover

There are several waypoints on the planet, some of which are connected. A rover can navigate between two waypoints A and B when A and B are connected. Interesting rocks can be found at any waypoint.

The rover can only analyze the rocks of a waypoint when it is at the waypoint. After the rover has analyzed a rock sample, it can transmit the results of this particular analysis to Earth. The transmission of the results of analysed rock samples can only be carried out at certain waypoints where the connection to Earth is good enough.

Each result is to be transferred via an individual action.

All actions have unit costs.

The goal is to analyze all rock samples and transfer the results to Earth.

Domain file

A domain file consists of:2

  • (define (domain DOMAINNAME)
  • a :requirements definition (use :strips :typing by default)
  • definitions of types (each parameter has a type)
  • definitions of predicates
  • definitions of operators (actions)
domain.pddl
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
(define (domain roverdomain)
(:requirements :strips :typing :adl)
(:types rover dish rock position)
(:predicates
(connected ?a ?b - position)
(has-dish ?a - position)
(has-rock ?a - position)
(has-rover ?a - position)
(occupied)
)

(:action navigate
:parameters (?a ?b - position)
:precondition (and
(has-rover ?a)
(connected ?a ?b)
)
:effect (and
(not (has-rover ?a))
(has-rover ?b)
)
)


(:action collect
:parameters (?a - position)
:precondition (and
(has-rover ?a)
(has-rock ?a)
(not (occupied))
)
:effect (and
(not (has-rock ?a))
(occupied)
)

)

(:action transmit
:parameters (?a - position)
:precondition (and
(occupied)
(has-rover ?a)
(has-dish ?a)
)

:effect (and
(not (occupied))
)
)

)

Problem file

A problem file consists of:3

  • (define (problem PROBLEMNAME)
  • declaration of which domain is needed for this problem
  • definitions of objects belonging to each type
  • definition of the initial state (list of state variables initially true)
  • definition of goal states (a formula like operator precondition)
problem.pddl
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
(define (problem roverproblem)
(:domain roverdomain)
(:objects
; dh - dish
; rv - rover
; rk - rock
a b c d e f g - position
)

(:init
(has-dish a)
(has-rock b)
(has-rock e)
(has-rock c)
(has-rock d)
(has-rover g)

(connected g f)
(connected f a)
(connected a b)
(connected b g)
(connected g b)
(connected b c)
(connected c b)
(connected e g)
(connected g e)
(connected d e)
(connected c d)
(connected d c)

)


(:goal
( and
(not (has-rock a))
(not (has-rock b))
(not (has-rock e))
(not (has-rock c))
(not (has-rock d))
(not (occupied))
)
)


)

Popular Planners

Fast Downward Planner

Fast Downward4 is a domain-independent classical planning system.

1
2
3
4
5
wget https://github.com/aibasel/downward/archive/release-20.06.0.tar.gz
tar -xvzf release-20.06.0.tar.gz
cd downward-release-20.06.0
./build.py # only once
./fast-downward.py --alias lama-first /path/to/domain.pddl /path/to/problem.pddl
[stdout]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
INFO     Running translator.
INFO translator stdin: None
INFO translator time limit: None
INFO translator memory limit: None
INFO translator command line string: /usr/bin/python3 builds/release/bin/translate/translate.py ../domain.pddl ../problem.pddl --sas-file output.sas
Parsing...
Parsing: [0.000s CPU, 0.001s wall-clock]
Normalizing task... [0.000s CPU, 0.000s wall-clock]
Instantiating...
Generating Datalog program... [0.000s CPU, 0.000s wall-clock]
Normalizing Datalog program...
Trivial rules: Converted to facts.
Normalizing Datalog program: [0.000s CPU, 0.002s wall-clock]
Preparing model... [0.000s CPU, 0.000s wall-clock]
Generated 10 rules.
Computing model... [0.000s CPU, 0.001s wall-clock]
64 relevant atoms
28 auxiliary atoms
92 final queue length
101 total queue pushes
Completing instantiation... [0.000s CPU, 0.001s wall-clock]
Instantiating: [0.000s CPU, 0.005s wall-clock]
Computing fact groups...
Finding invariants...
5 initial candidates
Finding invariants: [0.010s CPU, 0.001s wall-clock]
Checking invariant weight... [0.000s CPU, 0.000s wall-clock]
Instantiating groups... [0.000s CPU, 0.000s wall-clock]
Collecting mutex groups... [0.000s CPU, 0.000s wall-clock]
Choosing groups...
5 uncovered facts
Choosing groups: [0.000s CPU, 0.000s wall-clock]
Building translation key... [0.000s CPU, 0.000s wall-clock]
Computing fact groups: [0.010s CPU, 0.001s wall-clock]
Building STRIPS to SAS dictionary... [0.000s CPU, 0.000s wall-clock]
Building dictionary for full mutex groups... [0.000s CPU, 0.000s wall-clock]
Building mutex information...
Building mutex information: [0.000s CPU, 0.000s wall-clock]
Translating task...
Processing axioms...
Simplifying axioms... [0.000s CPU, 0.000s wall-clock]
Translator axioms removed by simplifying: 0
Computing negative axioms... [0.000s CPU, 0.000s wall-clock]
Processing axioms: [0.000s CPU, 0.000s wall-clock]
Translating task: [0.000s CPU, 0.001s wall-clock]
5 effect conditions simplified
0 implied preconditions added
Detecting unreachable propositions...
0 operators removed
0 axioms removed
1 propositions removed
Detecting unreachable propositions: [0.000s CPU, 0.000s wall-clock]
Reordering and filtering variables...
6 of 6 variables necessary.
0 of 1 mutex groups necessary.
17 of 17 operators necessary.
0 of 0 axiom rules necessary.
Reordering and filtering variables: [0.000s CPU, 0.000s wall-clock]
Translator variables: 6
Translator derived variables: 0
Translator facts: 17
Translator goal facts: 5
Translator mutex groups: 0
Translator total mutex groups size: 0
Translator operators: 17
Translator axioms: 0
Translator task size: 92
Translator peak memory: 26812 KB
Writing output... [0.000s CPU, 0.000s wall-clock]
Done! [0.010s CPU, 0.010s wall-clock]
translate exit code: 0

INFO Running search (release).
INFO search stdin: output.sas
INFO search time limit: None
INFO search memory limit: None
INFO search command line string: builds/release/bin/downward --evaluator 'hlm=lmcount(lm_factory=lm_rhw(reasonable_orders=true),transform=adapt_costs(one),pref=false)' --evaluator 'hff=ff(transform=adapt_costs(one))' --search 'lazy_greedy([hff,hlm],preferred=[hff,hlm],cost_type=one,reopen_closed=false)' --internal-plan-file sas_plan < output.sas
[t=4.9308e-05s, 9744 KB] reading input...
[t=0.000295154s, 9744 KB] done reading input!
[t=0.0019288s, 10000 KB] Initializing landmarks count heuristic...
[t=0.00200992s, 10000 KB] Initializing Exploration...
[t=0.00207028s, 10000 KB] Generating landmarks using the RPG/SAS+ approach
approx. reasonable orders
[t=0.00226699s, 10000 KB] approx. obedient reasonable orders
[t=0.00232234s, 10000 KB] Removed 0 reasonable or obedient reasonable orders
[t=0.0024036s, 10000 KB] Landmarks generation time: 0.000434502s
[t=0.00244563s, 10000 KB] Discovered 14 landmarks, of which 0 are disjunctive and 0 are conjunctive.
[t=0.00247662s, 10000 KB] 22 edges
[t=0.0025644s, 10000 KB] Simplifying 21 unary operators... done! [21 unary operators]
[t=0.00263706s, 10000 KB] time to simplify: 0.000104331s
[t=0.00269396s, 10000 KB] Initializing additive heuristic...
[t=0.00272805s, 10000 KB] Initializing FF heuristic...
[t=0.00285032s, 10000 KB] Building successor generator...done!
[t=0.00297551s, 10000 KB] peak memory difference for successor generator creation: 0 KB
[t=0.00300687s, 10000 KB] time for successor generation creation: 1.9058e-05s
[t=0.0030427s, 10000 KB] Variables: 6
[t=0.00307538s, 10000 KB] FactPairs: 17
[t=0.00310553s, 10000 KB] Bytes per state: 4
[t=0.00322581s, 10000 KB] Conducting lazy best first search, (real) bound = 2147483647
[t=0.00330731s, 10000 KB] 6 initial landmarks, 5 goal landmarks
[t=0.00336785s, 10000 KB] New best heuristic value for lmcount(lm_factory = lm_rhw(reasonable_orders = true), transform = adapt_costs(one), pref = false): 8
[t=0.00340958s, 10000 KB] New best heuristic value for ff(transform = adapt_costs(one)): 8
[t=0.00344425s, 10000 KB] g=0, 1 evaluated, 0 expanded
[t=0.00348597s, 10000 KB] Initial heuristic value for lmcount(lm_factory = lm_rhw(reasonable_orders = true), transform = adapt_costs(one), pref = false): 8
[t=0.00352082s, 10000 KB] Initial heuristic value for ff(transform = adapt_costs(one)): 8
[t=0.00356578s, 10000 KB] New best heuristic value for lmcount(lm_factory = lm_rhw(reasonable_orders = true), transform = adapt_costs(one), pref = false): 7
[t=0.00360315s, 10000 KB] g=1, 2 evaluated, 1 expanded
[t=0.00365184s, 10000 KB] New best heuristic value for ff(transform = adapt_costs(one)): 7
[t=0.00369002s, 10000 KB] g=2, 3 evaluated, 2 expanded
[t=0.00378585s, 10000 KB] New best heuristic value for lmcount(lm_factory = lm_rhw(reasonable_orders = true), transform = adapt_costs(one), pref = false): 6
[t=0.00382462s, 10000 KB] g=3, 9 evaluated, 8 expanded
[t=0.00398096s, 10000 KB] New best heuristic value for lmcount(lm_factory = lm_rhw(reasonable_orders = true), transform = adapt_costs(one), pref = false): 5
[t=0.00402012s, 10000 KB] New best heuristic value for ff(transform = adapt_costs(one)): 6
[t=0.0040531s, 10000 KB] g=10, 25 evaluated, 24 expanded
[t=0.00413626s, 10000 KB] New best heuristic value for lmcount(lm_factory = lm_rhw(reasonable_orders = true), transform = adapt_costs(one), pref = false): 4
[t=0.00417406s, 10000 KB] g=12, 31 evaluated, 30 expanded
[t=0.00430784s, 10000 KB] New best heuristic value for ff(transform = adapt_costs(one)): 5
[t=0.00435535s, 10000 KB] g=17, 43 evaluated, 42 expanded
[t=0.00439819s, 10000 KB] New best heuristic value for lmcount(lm_factory = lm_rhw(reasonable_orders = true), transform = adapt_costs(one), pref = false): 3
[t=0.0044344s, 10000 KB] New best heuristic value for ff(transform = adapt_costs(one)): 4
[t=0.00446531s, 10000 KB] g=18, 44 evaluated, 43 expanded
[t=0.00453552s, 10000 KB] New best heuristic value for lmcount(lm_factory = lm_rhw(reasonable_orders = true), transform = adapt_costs(one), pref = false): 2
[t=0.00457285s, 10000 KB] g=21, 49 evaluated, 48 expanded
[t=0.00465162s, 10000 KB] New best heuristic value for ff(transform = adapt_costs(one)): 3
[t=0.00468935s, 10000 KB] g=24, 56 evaluated, 55 expanded
[t=0.00473399s, 10000 KB] New best heuristic value for ff(transform = adapt_costs(one)): 2
[t=0.00477107s, 10000 KB] g=25, 57 evaluated, 56 expanded
[t=0.00481367s, 10000 KB] New best heuristic value for lmcount(lm_factory = lm_rhw(reasonable_orders = true), transform = adapt_costs(one), pref = false): 1
[t=0.00485071s, 10000 KB] New best heuristic value for ff(transform = adapt_costs(one)): 1
[t=0.00488327s, 10000 KB] g=26, 58 evaluated, 57 expanded
[t=0.00495006s, 10000 KB] Solution found!
[t=0.00498952s, 10000 KB] Actual search time: 0.00167119s
navigate g b (1)
navigate b c (1)
navigate c d (1)
collect d (1)
navigate d e (1)
navigate e g (1)
navigate g f (1)
navigate f a (1)
transmit a (1)
navigate a b (1)
navigate b c (1)
collect c (1)
navigate c b (1)
navigate b g (1)
navigate g f (1)
navigate f a (1)
transmit a (1)
navigate a b (1)
navigate b g (1)
navigate g e (1)
collect e (1)
navigate e g (1)
navigate g f (1)
navigate f a (1)
transmit a (1)
navigate a b (1)
collect b (1)
navigate b g (1)
navigate g f (1)
navigate f a (1)
transmit a (1)
[t=0.00502718s, 10000 KB] Plan length: 31 step(s).
[t=0.00502718s, 10000 KB] Plan cost: 31
[t=0.00502718s, 10000 KB] Expanded 62 state(s).
[t=0.00502718s, 10000 KB] Reopened 0 state(s).
[t=0.00502718s, 10000 KB] Evaluated 63 state(s).
[t=0.00502718s, 10000 KB] Evaluations: 126
[t=0.00502718s, 10000 KB] Generated 125 state(s).
[t=0.00502718s, 10000 KB] Dead ends: 0 state(s).
[t=0.00502718s, 10000 KB] Number of registered states: 63
[t=0.00502718s, 10000 KB] Int hash set load factor: 63/64 = 0.984375
[t=0.00502718s, 10000 KB] Int hash set resizes: 6
[t=0.00502718s, 10000 KB] Search time: 0.00180231s
[t=0.00502718s, 10000 KB] Total time: 0.00502718s
Solution found.
Peak memory: 10000 KB
Remove intermediate file output.sas
search exit code: 0

PDDL4J

The purpose of PDDL4J5 is to facilitate the development of JAVA tools for Automated Planning based on PDDL language (Planning Domain Description Language). Automated planning and scheduling, in the relevant literature often denoted as simply planning, is a branch of artificial intelligence that concerns the realization of strategies or action sequences, typically for execution by intelligent agents, autonomous robots and unmanned vehicles.[^1]

1
2
3
wget https://github.com/pellierd/pddl4j/releases/download/v3.8.3/PDDL4J-v3.8.3.zip
unzip PDDL4J-v3.8.3.zip
java -jar pddl4j-3.8.3.jar -p 0 -o domain.pddl -f problem.pddl
  • -p 0 for HSP (default planner)
  • -p 1 for FF
[stdout]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
parsing domain file "domain.pddl" done successfully
parsing problem file "problem.pddl" done successfully

encoding problem done successfully (17 ops, 12 facts)
* starting A*
* A* succeeded

found plan as follows:

00: (navigate g e) [1]
01: ( collect e) [1]
02: (navigate e g) [1]
03: (navigate g f) [1]
04: (navigate f a) [1]
05: ( transmit a) [1]
06: (navigate a b) [1]
07: (navigate b c) [1]
08: ( collect c) [1]
09: (navigate c b) [1]
10: (navigate b g) [1]
11: (navigate g f) [1]
12: (navigate f a) [1]
13: ( transmit a) [1]
14: (navigate a b) [1]
15: ( collect b) [1]
16: (navigate b g) [1]
17: (navigate g f) [1]
18: (navigate f a) [1]
19: ( transmit a) [1]
20: (navigate a b) [1]
21: (navigate b c) [1]
22: (navigate c d) [1]
23: ( collect d) [1]
24: (navigate d e) [1]
25: (navigate e g) [1]
26: (navigate g f) [1]
27: (navigate f a) [1]
28: ( transmit a) [1]

plan total cost: 29.00


time spent: 0.11 seconds parsing
0.05 seconds encoding
0.05 seconds searching
0.20 seconds total time

memory used: -0.00 MBytes for problem representation
-0.00 MBytes for searching
-0.00 MBytes total

Online Planner

PDDL Editor

editor.planning.domains is a fully featured PDDL editor. The functionality is continually changing, but currently it boasts features such as syntax highlighting, code folding, PDDL-specific auto-completion, multi-tab support, etc.

You can switch the default satisfactory solver with an optimal solver by simply replacing the Custom Planner URL with http://fd-solver.herokuapp.com.

If everything goes fine, you can find the plan in a new file on the left panel.

GUI Planner

PDDL4GUI

PDDL4GUI6 is a small application written in Java that provides a graphical interface to the PDDL4J library. PDDL4GUI offers:

  • A graphical interface for solving planning problems with the PDDL4J library.
  • A graphical interface for solving planning problems through PDDL4J webservice and RESTFull API.
  • Anytime behavior for compatible planners.
  • The integration of VAL (The plan validation system) which offers the possibility to test the validity of the plans provided by PDDL4J.

After cloning the git repository, simply run java -javaagent:pddl4gui-1.0.jar -server -Xms2048m -Xmx2048m -jar pddl4gui-1.0.jar -LOCAL or run the provided shell script ./pddl4gui_loc.sh.

Resources


  1. Patrik Haslum @ ANU↩︎

  2. Principles of AI Planning - domain files↩︎

  3. Principles of AI Planning - problem files↩︎

  4. Downward Planner Git Repository↩︎

  5. PDDL4J Git Repository↩︎

  6. PDDL4GUI Git Repository↩︎

At the time of writing, this "feature" cannot be disabled without a dedicated chrome extension1. And of course removing each item one by one is unreasonable.

Hence the following JS snippet iterate over each item in the list and clicks the delete button.

Usage

  1. Go to the search engine settings chrome://settings/searchEngines.
  2. Open the Developer Tools by clicking F12 or CTRL+SHIFT+I.
  3. Copy the script below and paste it in the Javascript console tab.
  4. Fire Away.

Snippet

A slight delay has been added between clicks since after each action the browser takes a moment to render the view. feel free to adjust the sleep at line 16 as you see fit.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
const otherEngines = document.querySelector("body > settings-ui")
.shadowRoot.querySelector("#main")
.shadowRoot.querySelector("settings-basic-page")
.shadowRoot.querySelector("#basicPage > settings-section.expanded > settings-search-page")
.shadowRoot.querySelector("#pages > settings-subpage > settings-search-engines-page")
.shadowRoot.querySelector("#otherEngines").shadowRoot

let n = otherEngines.querySelector('iron-list').childElementCount - 1;
let rmbtn = otherEngines.querySelector('#frb0')
.shadowRoot.querySelector('#delete')

const sleep = (ms) => new Promise(resolve => setTimeout(resolve, ms));

while(n--) {
rmbtn.click();
await sleep(2000);
}

  1. Don't add custom search engines by Greg Sadetsky,↩︎

Python has been always the ultimate glue language in various fields due to it's intuitive syntax and a huge community that support different high-level tools and libraries. But it's no secret that python is extremely slow compared to compiled languages like C.

Luckily, Python can easily interface with low-level languages to gain the best of both worlds. This post will show how to find and elevate some of the performance bottlenecks in your code.

In mathematics, the Fibonacci numbers, commonly denoted \(F_n\), form a sequence, called the Fibonacci sequence, such that each number is the sum of the two preceding ones, starting from 0 and 1. That is,

\[\begin{align*} &\quad F_0=0, F_1= 1,\\ &F_n=F_{n-1} + F_{n-2}, &&\textbf{n} > 1 \end{align*}\]

The beginning of the sequence is thus: \(0,\;1,\;1,\;2,\;3,\;5,\;8,\;13,\;21,\;34,\;55,\;89,\;144,\; \ldots\)

Fibonacci numberWikipedia

For the demonstration purposes , A grossly inefficient implementation of Fibonacci sequence will be used as a toy example:

fib.py
1
2
3
4
def f(x):
return f(x - 1) + f(x - 2) if x > 2 else 1

print(f(40))

Identify bottlenecks

Python has a couple of built-in profilers that can be used to benchmark the performance of your code: profile and cProfile. profile is written in pure python which in return adds a significant overhead and wastes more time than cProfile, which is a C extension with minimal overhead.

To run cProfile on your script, simply type:

python -m cProfile fib.py

102334155
204668313 function calls (5 primitive calls) in 76.602 seconds

Ordered by: standard name

ncalls tottime percall cumtime percall filename:lineno(function)
1 0.011 0.011 76.602 76.602 fib.py:6(<module>)
204668309/1 76.591 0.000 76.591 76.591 fib.py:6(f)
1 0.000 0.000 76.602 76.602 {built-in method builtins.exec}
1 0.000 0.000 0.000 0.000 {built-in method builtins.print}
1 0.000 0.000 0.000 0.000 {method 'disable' of '_lsprof.Profiler' objects}

To calculate the 40th fibonacci number in the sequence, the script spent 76.602 seconds in f(x) strongly hinting that this causes a serious bottleneck. 1

What can we do about it?

Cython

Cython is an optimising static compiler for both the Python programming language and the extended Cython programming language (based on Pyrex). It makes writing C extensions for Python as easy as Python itself.

In a nutshell, Cython will transpile our python code to C then compile it into a shared object.

First, Write the function in a new file fib.pyx providing as much type hints as possible

1
2
def f(int x): # type hint
return f(x - 1) + f(x - 2) if x > 2 else 1

Create a new file setup.py with the following:

1
2
3
4
5
6
from setuptools import setup
from Cython.Build import cythonize

setup(
ext_modules=cythonize("fib.pyx")
)

Finally run setup.py with the following arguments:

python setup.py build_ext --inplace

The previous step generated the required shared object and the necessary interfaces that integrates seamlessly with python using a regular import statement.

1
2
import fib
print(fib.f(40))

re-run cProfile

102334155
97 function calls in 4.156 seconds

Ordered by: standard name

ncalls tottime percall cumtime percall filename:lineno(function)
1 0.000 0.000 0.000 0.000 <frozen importlib._bootstrap>:103(release)
1 0.000 0.000 0.000 0.000 <frozen importlib._bootstrap>:143(__init__)
1 0.000 0.000 0.000 0.000 <frozen importlib._bootstrap>:147(__enter__)
1 0.000 0.000 0.000 0.000 <frozen importlib._bootstrap>:151(__exit__)
1 0.000 0.000 0.000 0.000 <frozen importlib._bootstrap>:157(_get_module_lock)
1 0.000 0.000 0.000 0.000 <frozen importlib._bootstrap>:176(cb)
2 0.000 0.000 0.000 0.000 <frozen importlib._bootstrap>:211(_call_with_frames_removed)
4 0.000 0.000 0.000 0.000 <frozen importlib._bootstrap>:222(_verbose_message)
1 0.000 0.000 0.000 0.000 <frozen importlib._bootstrap>:342(__init__)
1 0.000 0.000 0.000 0.000 <frozen importlib._bootstrap>:376(cached)
1 0.000 0.000 0.000 0.000 <frozen importlib._bootstrap>:389(parent)
1 0.000 0.000 0.000 0.000 <frozen importlib._bootstrap>:397(has_location)
1 0.000 0.000 0.000 0.000 <frozen importlib._bootstrap>:477(_init_module_attrs)
1 0.000 0.000 0.000 0.000 <frozen importlib._bootstrap>:549(module_from_spec)
1 0.000 0.000 0.000 0.000 <frozen importlib._bootstrap>:58(__init__)
1 0.000 0.000 0.000 0.000 <frozen importlib._bootstrap>:650(_load_unlocked)
1 0.000 0.000 0.000 0.000 <frozen importlib._bootstrap>:725(find_spec)
1 0.000 0.000 0.000 0.000 <frozen importlib._bootstrap>:78(acquire)
1 0.000 0.000 0.000 0.000 <frozen importlib._bootstrap>:800(find_spec)
3 0.000 0.000 0.000 0.000 <frozen importlib._bootstrap>:863(__enter__)
3 0.000 0.000 0.000 0.000 <frozen importlib._bootstrap>:867(__exit__)
1 0.000 0.000 0.000 0.000 <frozen importlib._bootstrap>:890(_find_spec)
1 0.000 0.000 0.000 0.000 <frozen importlib._bootstrap>:956(_find_and_load_unlocked)
1 0.000 0.000 0.000 0.000 <frozen importlib._bootstrap>:986(_find_and_load)
1 0.000 0.000 0.000 0.000 <frozen importlib._bootstrap_external>:1088(__init__)
1 0.000 0.000 0.000 0.000 <frozen importlib._bootstrap_external>:1099(create_module)
1 0.000 0.000 0.000 0.000 <frozen importlib._bootstrap_external>:1107(exec_module)
1 0.000 0.000 0.000 0.000 <frozen importlib._bootstrap_external>:1265(_path_importer_cache)
1 0.000 0.000 0.000 0.000 <frozen importlib._bootstrap_external>:1302(_get_spec)
1 0.000 0.000 0.000 0.000 <frozen importlib._bootstrap_external>:1334(find_spec)
1 0.000 0.000 0.000 0.000 <frozen importlib._bootstrap_external>:1426(_get_spec)
1 0.000 0.000 0.000 0.000 <frozen importlib._bootstrap_external>:1431(find_spec)
1 0.000 0.000 0.000 0.000 <frozen importlib._bootstrap_external>:40(_relax_case)
1 0.000 0.000 0.000 0.000 <frozen importlib._bootstrap_external>:424(_get_cached)
1 0.000 0.000 0.000 0.000 <frozen importlib._bootstrap_external>:62(_path_join)
1 0.000 0.000 0.000 0.000 <frozen importlib._bootstrap_external>:629(spec_from_file_location)
1 0.000 0.000 0.000 0.000 <frozen importlib._bootstrap_external>:64(<listcomp>)
2 0.000 0.000 0.000 0.000 <frozen importlib._bootstrap_external>:80(_path_stat)
1 0.000 0.000 0.000 0.000 <frozen importlib._bootstrap_external>:90(_path_is_mode_type)
1 0.000 0.000 0.000 0.000 <frozen importlib._bootstrap_external>:99(_path_isfile)
1 0.000 0.000 4.156 4.156 fib.py:10(<module>)
5 0.000 0.000 0.000 0.000 {built-in method _imp.acquire_lock}
1 0.000 0.000 0.000 0.000 {built-in method _imp.create_dynamic}
1 0.000 0.000 0.000 0.000 {built-in method _imp.exec_dynamic}
1 0.000 0.000 0.000 0.000 {built-in method _imp.is_builtin}
1 0.000 0.000 0.000 0.000 {built-in method _imp.is_frozen}
5 0.000 0.000 0.000 0.000 {built-in method _imp.release_lock}
2 0.000 0.000 0.000 0.000 {built-in method _thread.allocate_lock}
2 0.000 0.000 0.000 0.000 {built-in method _thread.get_ident}
1 0.000 0.000 4.156 4.156 {built-in method builtins.exec}
6 0.000 0.000 0.000 0.000 {built-in method builtins.getattr}
3 0.000 0.000 0.000 0.000 {built-in method builtins.hasattr}
1 0.000 0.000 0.000 0.000 {built-in method builtins.isinstance}
1 0.000 0.000 0.000 0.000 {built-in method builtins.print}
1 0.000 0.000 0.000 0.000 {built-in method posix.fspath}
1 0.000 0.000 0.000 0.000 {built-in method posix.getcwd}
2 0.000 0.000 0.000 0.000 {built-in method posix.stat}
1 4.155 4.155 4.155 4.155 {fib.f}
1 0.000 0.000 0.000 0.000 {method 'disable' of '_lsprof.Profiler' objects}
2 0.000 0.000 0.000 0.000 {method 'endswith' of 'str' objects}
2 0.000 0.000 0.000 0.000 {method 'get' of 'dict' objects}
1 0.000 0.000 0.000 0.000 {method 'join' of 'str' objects}
1 0.000 0.000 0.000 0.000 {method 'pop' of 'dict' objects}
3 0.000 0.000 0.000 0.000 {method 'rpartition' of 'str' objects}
2 0.000 0.000 0.000 0.000 {method 'rstrip' of 'str' objects}

Went down from 76.602 seconds to 4.156 almost 18x speed-up.

Although this approach is much easier, but the generated C code is part of large generic boilerplate and results in a noticeable overhead. Therefore, it's highly recommended to provide as much type hints as possible before compilation process.

ctypes

ctypes is a foreign function library for Python. It provides C compatible data types, and allows calling functions in DLLs or shared libraries. It can be used to wrap these libraries in pure Python.

First, Rewrite the performance critical functions in C or C++.

1
2
3
extern "C" int f(int x) {
return x > 2 ? f(x - 1) + f(x - 2) : 1;
}

extern "C" tells the compiler to avoid mangling the function name. which will work with simple function prototypes, but one-to-one mapping between C++ classes and python classes is not possible without an interface library like pybind11.

Then compile it into a shared object:

clang++ -shared -o fib.so fib.cpp

Lastly we can call any function from the shared object inside python:

1
2
3
4
import ctypes
fib = ctypes.CDLL('./fib.so')

print(fib.f(40))

Running cProfile again yields a few extra system calls that loads the shared object:

102334155
1265 function calls (1242 primitive calls) in 0.617 seconds

Ordered by: standard name

ncalls tottime percall cumtime percall filename:lineno(function)
1 0.000 0.000 0.000 0.000 <frozen importlib._bootstrap>:1017(_handle_fromlist)
6 0.000 0.000 0.000 0.000 <frozen importlib._bootstrap>:103(release)
5 0.000 0.000 0.000 0.000 <frozen importlib._bootstrap>:143(__init__)
5 0.000 0.000 0.000 0.000 <frozen importlib._bootstrap>:147(__enter__)
5 0.000 0.000 0.000 0.000 <frozen importlib._bootstrap>:151(__exit__)
6 0.000 0.000 0.000 0.000 <frozen importlib._bootstrap>:157(_get_module_lock)
5 0.000 0.000 0.000 0.000 <frozen importlib._bootstrap>:176(cb)
1 0.000 0.000 0.000 0.000 <frozen importlib._bootstrap>:194(_lock_unlock_module)
7/1 0.000 0.000 0.002 0.002 <frozen importlib._bootstrap>:211(_call_with_frames_removed)
75 0.000 0.000 0.000 0.000 <frozen importlib._bootstrap>:222(_verbose_message)
5 0.000 0.000 0.000 0.000 <frozen importlib._bootstrap>:342(__init__)
3 0.000 0.000 0.000 0.000 <frozen importlib._bootstrap>:35(_new_module)
8 0.000 0.000 0.000 0.000 <frozen importlib._bootstrap>:376(cached)
5 0.000 0.000 0.000 0.000 <frozen importlib._bootstrap>:389(parent)
5 0.000 0.000 0.000 0.000 <frozen importlib._bootstrap>:397(has_location)
5 0.000 0.000 0.000 0.000 <frozen importlib._bootstrap>:477(_init_module_attrs)
5 0.000 0.000 0.001 0.000 <frozen importlib._bootstrap>:549(module_from_spec)
5 0.000 0.000 0.000 0.000 <frozen importlib._bootstrap>:58(__init__)
5/1 0.000 0.000 0.002 0.002 <frozen importlib._bootstrap>:650(_load_unlocked)
5 0.000 0.000 0.000 0.000 <frozen importlib._bootstrap>:725(find_spec)
6 0.000 0.000 0.000 0.000 <frozen importlib._bootstrap>:78(acquire)
5 0.000 0.000 0.000 0.000 <frozen importlib._bootstrap>:800(find_spec)
15 0.000 0.000 0.000 0.000 <frozen importlib._bootstrap>:863(__enter__)
15 0.000 0.000 0.000 0.000 <frozen importlib._bootstrap>:867(__exit__)
5 0.000 0.000 0.001 0.000 <frozen importlib._bootstrap>:890(_find_spec)
5/1 0.000 0.000 0.003 0.003 <frozen importlib._bootstrap>:956(_find_and_load_unlocked)
5/1 0.000 0.000 0.003 0.003 <frozen importlib._bootstrap>:986(_find_and_load)
3 0.000 0.000 0.000 0.000 <frozen importlib._bootstrap_external>:1010(path_stats)
1 0.000 0.000 0.000 0.000 <frozen importlib._bootstrap_external>:104(_path_isdir)
2 0.000 0.000 0.000 0.000 <frozen importlib._bootstrap_external>:1088(__init__)
2 0.000 0.000 0.000 0.000 <frozen importlib._bootstrap_external>:1099(create_module)
2 0.000 0.000 0.000 0.000 <frozen importlib._bootstrap_external>:1107(exec_module)
1 0.000 0.000 0.000 0.000 <frozen importlib._bootstrap_external>:1252(_path_hooks)
19 0.000 0.000 0.000 0.000 <frozen importlib._bootstrap_external>:1265(_path_importer_cache)
5 0.000 0.000 0.000 0.000 <frozen importlib._bootstrap_external>:1302(_get_spec)
5 0.000 0.000 0.000 0.000 <frozen importlib._bootstrap_external>:1334(find_spec)
1 0.000 0.000 0.000 0.000 <frozen importlib._bootstrap_external>:1394(__init__)
8 0.000 0.000 0.000 0.000 <frozen importlib._bootstrap_external>:1400(<genexpr>)
5 0.000 0.000 0.000 0.000 <frozen importlib._bootstrap_external>:1426(_get_spec)
15 0.000 0.000 0.000 0.000 <frozen importlib._bootstrap_external>:1431(find_spec)
1 0.000 0.000 0.000 0.000 <frozen importlib._bootstrap_external>:1479(_fill_cache)
1 0.000 0.000 0.000 0.000 <frozen importlib._bootstrap_external>:1520(path_hook_for_FileFinder)
6 0.000 0.000 0.000 0.000 <frozen importlib._bootstrap_external>:294(cache_from_source)
15 0.000 0.000 0.000 0.000 <frozen importlib._bootstrap_external>:40(_relax_case)
5 0.000 0.000 0.000 0.000 <frozen importlib._bootstrap_external>:424(_get_cached)
3 0.000 0.000 0.000 0.000 <frozen importlib._bootstrap_external>:456(_check_name_wrapper)
3 0.000 0.000 0.000 0.000 <frozen importlib._bootstrap_external>:493(_classify_pyc)
3 0.000 0.000 0.000 0.000 <frozen importlib._bootstrap_external>:51(_unpack_uint32)
3 0.000 0.000 0.000 0.000 <frozen importlib._bootstrap_external>:554(_validate_hash_pyc)
3 0.000 0.000 0.000 0.000 <frozen importlib._bootstrap_external>:578(_compile_bytecode)
71 0.000 0.000 0.000 0.000 <frozen importlib._bootstrap_external>:62(_path_join)
5 0.000 0.000 0.000 0.000 <frozen importlib._bootstrap_external>:629(spec_from_file_location)
71 0.000 0.000 0.000 0.000 <frozen importlib._bootstrap_external>:64(<listcomp>)
6 0.000 0.000 0.000 0.000 <frozen importlib._bootstrap_external>:68(_path_split)
3 0.000 0.000 0.000 0.000 <frozen importlib._bootstrap_external>:774(create_module)
3/1 0.000 0.000 0.002 0.002 <frozen importlib._bootstrap_external>:777(exec_module)
28 0.000 0.000 0.000 0.000 <frozen importlib._bootstrap_external>:80(_path_stat)
3 0.000 0.000 0.000 0.000 <frozen importlib._bootstrap_external>:849(get_code)
9 0.000 0.000 0.000 0.000 <frozen importlib._bootstrap_external>:90(_path_is_mode_type)
3 0.000 0.000 0.000 0.000 <frozen importlib._bootstrap_external>:939(__init__)
3 0.000 0.000 0.000 0.000 <frozen importlib._bootstrap_external>:964(get_filename)
6 0.000 0.000 0.000 0.000 <frozen importlib._bootstrap_external>:969(get_data)
8 0.000 0.000 0.000 0.000 <frozen importlib._bootstrap_external>:99(_path_isfile)
1 0.000 0.000 0.000 0.000 <frozen zipimport>:63(__init__)
1 0.000 0.000 0.002 0.002 __init__.py:1(<module>)
2 0.000 0.000 0.000 0.000 __init__.py:101(CFunctionType)
14 0.000 0.000 0.000 0.000 __init__.py:141(_check_size)
1 0.000 0.000 0.000 0.000 __init__.py:153(py_object)
1 0.000 0.000 0.000 0.000 __init__.py:162(c_short)
1 0.000 0.000 0.000 0.000 __init__.py:166(c_ushort)
1 0.000 0.000 0.000 0.000 __init__.py:170(c_long)
1 0.000 0.000 0.000 0.000 __init__.py:174(c_ulong)
1 0.000 0.000 0.000 0.000 __init__.py:183(c_int)
1 0.000 0.000 0.000 0.000 __init__.py:187(c_uint)
1 0.000 0.000 0.000 0.000 __init__.py:191(c_float)
1 0.000 0.000 0.000 0.000 __init__.py:195(c_double)
1 0.000 0.000 0.000 0.000 __init__.py:199(c_longdouble)
1 0.000 0.000 0.000 0.000 __init__.py:220(c_ubyte)
1 0.000 0.000 0.000 0.000 __init__.py:227(c_byte)
1 0.000 0.000 0.000 0.000 __init__.py:232(c_char)
1 0.000 0.000 0.000 0.000 __init__.py:237(c_char_p)
1 0.000 0.000 0.000 0.000 __init__.py:243(c_void_p)
1 0.000 0.000 0.000 0.000 __init__.py:248(c_bool)
1 0.000 0.000 0.000 0.000 __init__.py:253(c_wchar_p)
1 0.000 0.000 0.000 0.000 __init__.py:258(c_wchar)
1 0.000 0.000 0.000 0.000 __init__.py:261(_reset_cache)
1 0.000 0.000 0.000 0.000 __init__.py:318(CDLL)
2 0.000 0.000 0.001 0.001 __init__.py:339(__init__)
2 0.000 0.000 0.000 0.000 __init__.py:367(_FuncPtr)
1 0.000 0.000 0.000 0.000 __init__.py:383(__getattr__)
1 0.000 0.000 0.000 0.000 __init__.py:390(__getitem__)
1 0.000 0.000 0.000 0.000 __init__.py:396(PyDLL)
1 0.000 0.000 0.000 0.000 __init__.py:436(LibraryLoader)
2 0.000 0.000 0.000 0.000 __init__.py:437(__init__)
3 0.000 0.000 0.000 0.000 __init__.py:498(PYFUNCTYPE)
3 0.000 0.000 0.000 0.000 __init__.py:499(CFunctionType)
2 0.000 0.000 0.000 0.000 __init__.py:75(CFUNCTYPE)
1 0.000 0.000 0.000 0.000 _endian.py:1(<module>)
1 0.000 0.000 0.000 0.000 _endian.py:23(_swapped_meta)
1 0.000 0.000 0.000 0.000 _endian.py:46(BigEndianStructure)
1 0.613 0.613 0.617 0.617 fib.py:1(<module>)
1 0.000 0.000 0.000 0.000 struct.py:3(<module>)
2 0.000 0.000 0.000 0.000 {built-in method _ctypes.POINTER}
2 0.001 0.001 0.001 0.001 {built-in method _ctypes.dlopen}
38 0.000 0.000 0.000 0.000 {built-in method _ctypes.sizeof}
3 0.000 0.000 0.000 0.000 {built-in method _imp._fix_co_filename}
26 0.000 0.000 0.000 0.000 {built-in method _imp.acquire_lock}
2 0.000 0.000 0.000 0.000 {built-in method _imp.create_dynamic}
2 0.000 0.000 0.000 0.000 {built-in method _imp.exec_dynamic}
4 0.000 0.000 0.000 0.000 {built-in method _imp.is_builtin}
5 0.000 0.000 0.000 0.000 {built-in method _imp.is_frozen}
26 0.000 0.000 0.000 0.000 {built-in method _imp.release_lock}
3 0.000 0.000 0.000 0.000 {built-in method _imp.source_hash}
18 0.000 0.000 0.000 0.000 {built-in method _struct.calcsize}
10 0.000 0.000 0.000 0.000 {built-in method _thread.allocate_lock}
12 0.000 0.000 0.000 0.000 {built-in method _thread.get_ident}
30 0.001 0.000 0.001 0.000 {built-in method builtins.__build_class__}
4/1 0.000 0.000 0.617 0.617 {built-in method builtins.exec}
30 0.000 0.000 0.000 0.000 {built-in method builtins.getattr}
26 0.000 0.000 0.000 0.000 {built-in method builtins.hasattr}
31 0.000 0.000 0.000 0.000 {built-in method builtins.isinstance}
12 0.000 0.000 0.000 0.000 {built-in method builtins.len}
1 0.000 0.000 0.000 0.000 {built-in method builtins.print}
2 0.000 0.000 0.000 0.000 {built-in method builtins.setattr}
3 0.000 0.000 0.000 0.000 {built-in method from_bytes}
6 0.000 0.000 0.000 0.000 {built-in method io.open_code}
3 0.000 0.000 0.000 0.000 {built-in method marshal.loads}
11 0.000 0.000 0.000 0.000 {built-in method posix.fspath}
4 0.000 0.000 0.000 0.000 {built-in method posix.getcwd}
1 0.000 0.000 0.000 0.000 {built-in method posix.listdir}
28 0.000 0.000 0.000 0.000 {built-in method posix.stat}
2 0.000 0.000 0.000 0.000 {method 'clear' of 'dict' objects}
1 0.000 0.000 0.000 0.000 {method 'disable' of '_lsprof.Profiler' objects}
7 0.000 0.000 0.000 0.000 {method 'endswith' of 'str' objects}
3 0.000 0.000 0.000 0.000 {method 'extend' of 'list' objects}
10 0.000 0.000 0.000 0.000 {method 'get' of 'dict' objects}
77 0.000 0.000 0.000 0.000 {method 'join' of 'str' objects}
9 0.000 0.000 0.000 0.000 {method 'pop' of 'dict' objects}
6 0.000 0.000 0.000 0.000 {method 'read' of '_io.BufferedReader' objects}
37 0.000 0.000 0.000 0.000 {method 'rpartition' of 'str' objects}
148 0.000 0.000 0.000 0.000 {method 'rstrip' of 'str' objects}
5 0.000 0.000 0.000 0.000 {method 'startswith' of 'str' objects}

We went from 76.602 seconds to 0.612 almost 125x speed-up!


  1. obviously since it's the only function.↩︎

Decorators allow you to attach new functionality to a method without modifying it's behavior. This can be easily implemented in python because functions are treated as first class citizens (i.e a can be passed as arguments or returned from functions).

To put in simple terms:

A Decorator is a function the takes a function and returns a function.

They are used extensively in some popular frameworks like Flask.

Dummy Decorator

This is a simple decorator that prints a statement before and after a function is called.

Declare

1
2
3
4
5
6
7
8
def dec(f: Callable) -> Callable:
def g(*args, **kwargs):
print('Function starts')
r = f(*args, **kwargs)
print(f) # print function name and location in memory
print('Function ends')
return r # return result
return g # returns a new "decorated" function
  • Line 1: We define a new function (which will soon be our decorator) called dec which takes a function f as a parameter. I have added few type hints using import typing but it's not necessary and not enforced by the interpreter.

  • Line 2: We define a new inner function g which takes all the ordinary arguments and keyword arguments that function f takes.

  • Line 3: Just an example of something that happens before executing function f.

  • Line 4: Call function f with all of it's arguments and store result in variable r.

  • Line 5: Just and example of something that happens after executing function f.

  • Line 6: Returns the result of function f in order to keep it working as intended.

  • Line 7: Returns the newly decorated function g.

Usage

Now let's decorate a simple add function with the new decorator:

1
2
3
4
5
6
@dec
def add(x: float, y: float):
return x + y

add(5, 6)
print(add)

Output

1
2
3
4
5
Function starts
<function add at 0x7f6735d528b0>
Function ends
11
<function dec.<locals>.g at 0x7f6735d52940>

The difference in function name and memory address (line 2 & line 5) will be discussed below.

Timer Decorator

Here is an applicable example of a decorator that enables you to easily determine how long does a function takes in order to finish execution.

Declare

1
2
3
4
5
6
7
8
def timer(f: Callable) -> Callable:
def g(*args, **kwargs):
t_start = time.monotonic()
r = f(*args, **kwargs)
t_end = time.monotonic()
print(f"It took {t_end - t_start} to execute \"{f.__name__}\" function")
return r
return g

Usage

You replace the @dec with @timer or even stack multiple decorators on top of each other:

1
2
3
4
5
6
7
@dec
@timer
def add(x: float, y: float):
return x + y

add(5, 6)
print(add)

Output

1
2
3
4
5
Function starts
It took 5.5779964895918965e-06 to execute "add" function
<function timer.<locals>.g at 0x7f1da16d2940>
Function ends
11
  • Line 1: Output of decorator @dec.
  • Line 2: Output of decorator @timer.
  • Line 3, 4: The rest of @dec's output.
  • Line 5: Output of function add.

Tracker Decorator

Let's assume you want to keep track of the output of different functions in some sort of a global set. This can be useful for some sort of a simple unit testing solution.

Declare

1
2
3
4
5
6
7
8
9
TEST = set()

def track(f: Callable) -> Callable:
def g(*args, **kwargs):
r = f(*args, **kwargs)
t = (f.__name__, args, kwargs, r)
TEST.add(t)
return r
return g

Not much different than the previous decorators, only is adding a tuple that contains the function name, arguments and result to a global set called TEST.

Usage

1
2
3
4
5
6
7
8
print(add(5, 6))
print(add(3, 7))
print(add(11, 17))
print(add)
print(STATE)

assert STATE == {('add', (11, 17), 28), ('add', (5, 6), 11), ('add', (3, 7), 10)}
print('All tests passed successfully')

If anything went wrong with the assert statement; the interpreter will halt execution and raise and assert exception. AssertionError

Output

1
2
3
4
5
6
11
10
28
<function track.<locals>.g at 0x7f01e1b399d0>
[('add', (5, 6), {}, 11), ('add', (3, 7), {}, 10), ('add', (11, 17), {}, 28)]
All tests passed successfully

functools.wraps

In order to add additional functionality to a method, the decorator generate a new function with a new name in a new memory address which might confuse some tools and debuggers.

To avoid renaming your function and keep it's original docstring, use wraps from functools:

1
2
3
4
5
6
7
8
9
10
11
from functools import wraps

def dec(f: Callable) -> Callable:
@wraps(f)
def g(*args, **kwargs):
print('Function starts')
r = f(*args, **kwargs)
print(f) # print function name and location in memory
print('Function ends')
return r # return result
return g

Every once and a while, I check my email's spam folder for fun phishing attempts and stumped upon one in particular that was rather interesting:

1
2
3
4
5
6
7
8
Title: [Some old password]

Actually, I placed a virus on the xXx vids (sex sites) site & guess what, you visited this web site to have fun. While you were viewing videos, your web browser started working as a Remote Desktop having a keylogger which gave me accessibility to your display and also cam recording.
Just after that, my software collected all your contacts from your Messenger, social networks, and email.
[Some old password] is one of your passwords.
if you send me $986 as a donation through Bitcoin, I will erase the recording immediately.
(search for in Google "how to buy bitcoin"). my BTC Address: [A brand new bitcoin wallet address with zero transactions]
If I don't get the BitCoins in 24hrs, I will definately send your video to all of your contacts, don't.reply to this email it's hacked. WxEQ

Of course it goes without saying, This is "definately"1 non-sense, yet you might ask how did he managed to get the old password?

This answer is from one of many data breaches that happens almost every few months. Almost every major company had a data breach in some point (Adobe, Dropbox, LinkedIn, ...) and you can check your email using one of the following services:

have i been pwned?

have i been pwned? checks if you have an account that has been compromised in a data breach and offer to notify you if your email appears in any public accounts dump or spam list.

Hacked Emails

Hacked Emails very similar to have i been pwned? but requires email verification before checking your email against it's database of public data breaches.

DeHashed

DeHashed is similar to the other solutions but it takes this process one step further by offers a cheap subscription plan that allows anyone to get the list of publicly plaintext password for any email address.

If you happen to receive a similar email, you can report the bitcoin address to:

Bitcoin Abuse Database

BitcoinAbuse.com is a public database of bitcoin addresses used by scammers, hackers, and criminals. Bitcoin is anonymous if used perfectly. Luckily, no one is perfect. Even hackers make mistakes. It only takes one slip to link stolen bitcoin to a hacker's their real identity. It is our hope that by making a public database of bitcoin addresses used by criminals it will be harder for criminals to convert the digital currency back into fiat money.


  1. The miss-spelling was intentional.↩︎