User attention sharing

CPU is a precious resource that must be shared between the processes concurrently running on a machine at a given time. Some operating systems of the past implemented this sharing using a technique called collaborative multitasking, which is based on the processes' explicitly relinquishing CPU control to the OS so that this control be passed on to other tasks. This can be very inefficient, as sharing cannot be controlled by the operating system, but depends on the good judgement of third party application programmers; furthermore, a faulty process that fails to yield CPU or hangs will collapse the whole system. So, modern OSs implement preemptive multitasking, in which the system scheduler can give or take CPU control without any special help from the processes. Usual implementations of preemptive multitasking group processes into two categories: IO-bound processes, which consume most of the time waiting for user input or dealing with secondary storage, and CPU-bound processes, which take up as much computing power as they are given. Some scheduling algorithms reward the least CPU-hungry processes by giving them higher priority to regain CPU.

In a desktop machine, user attention is as much of a precious shared resource as CPU is: concurrently living applications try to attract the user focus by displaying some visual effects or directly putting themselves on the forefront. In the early, more naïve days, applications could freely jump into the foreground of their own accord, which could quickly degrade into an all-out fight (specially if malware was involved) for the user's attention, or "attention thrashing", and render the computer unusable. This situation is reminiscent of the first candid collaborative multitasking systems; incidentally, attention thrashing led some OS vendors to change the behavior of some of their APIs to try to restrict the applications' freedom to steal focus from each other, though workarounds abound. In the web browser arena, attention thrashing can be even more daunting, and most users end up entirely blocking pop-ups and other forms of focus stealing.

As I see it, user attention should then be explicitly taken care of by the operating system in the same way as CPU control is; in fact, we can learn from the history of multitasking and move from the current "collaborative" situation to system-controlled scenarios where applications request attention and are given it based on attention availability and some measure of application fairness. So, applications that request attention very rarely and do so for justified motives (where this last attribute can be estimated indirectly by, say, recording the amount of time spent by the user on the application when this pops up) are ranked higher and can be given more leeway to call on the user. On the other hand, noisy applications are rapidly ranked low and will not be able to steal focus unless the user explicitly clicks on them.

Mass exhalation

How much bodily mass do we give out through breathing? The chemical reaction for aerobic respiration is

C₆H₁₂O₆ + 6O₂ → 6CO₂ + 6H₂O

The amount of carbon dioxide we exhale is then

6 mol CO₂ / mol glucose = 1.47 g CO₂ / g glucose.

Processing of fatty acids yields a different amount of exhaled CO₂. For instance, the oxidation of a saturated fatty acid is expressed as

C_nH_2nO₂ + (3n/2 − 1) O₂ → n CO₂ + n H₂O

yielding

44n/(14n + 32) g CO₂ / g C_nH_2nO₂.

This last expression also serves approximately for unsaturated fatty acids, since these are missing only a few lightweight hydrogen atoms with respect to the saturated acid with the same amount of carbon. Assuming most consumed fat is in the form of palmitate, we have a carbon dioxide yield of

2.75 g CO₂ / g fat;

Carbohydrates produce 4 kcal per gram, whereas fatty acid processing yields 9 kcal per gram of fat. While at rest, the human body takes 30% of the energy from carbohydrates and 70% from fat; so, this results in a combined production of carbon dioxide of

0.324 g CO₂ / kcal.

For a daily energy consumption rate around 2,500 kcal, 810 grams of carbon dioxide are then expelled through breathing. There is a experimental study by the USDA on the subject that unfortunately I haven't been able to find, but some sources cite it as reporting a value beween 445 and 450 liters of CO₂ (881-891 g) per day, which is in good agreement with our calculations.

The value calculated is not the answer to our original question about exhaled bodily mass: much of the oxygen in the CO₂ produced comes from the air rather than catabolized substances, specially in the case of fat. We will assume that all the oxygen coming from the burned substance goes to CO₂: under these conditions, the amount of bodily mass expelled through breathing is

0.933 g / g glucose,
0.875 g / g fat,

or, using the assumed ratios of carbohydrate and fat consumption,

0.138 g / kcal,

which yields 345 g for a typical daily energy consumption of 2,500 calories.

Generating permutation covers: part I

We investigate ways of efficiently generating minimal permutation covers for a set S of N elements. As we have already proved, such covers have size C(N,floor(N/2)). The following intermediate results reduce the problem to simpler terms.

Theorem. Assume that N is even and greater than zero. Let a be an an arbitrary element of S and Σ a minimal permutation cover of S − {a}. The set Σ' defined as

Σ' = {aσ, σa : σ in Σ}

is a minimal permutation cover of S.

Proof. Σ' is a permutation cover: let X be a subset of S; if a is not in X, X is covered by some permutation σ of Σ and a fortiori by σa in Σ'; if a belongs to X, some σ in Σ covers X − {a} and then aσ in Σ' covers X. Σ' is minimal as |Σ'| = 2|Σ| = 2 C(N − 1, floor((N − 1)/2)) = 2 C(N − 1, N/2 − 1) = C(N,N/2) = C(N,floor(N/2)), where the equalities depend on basic properties of binomial coefficients and the fact that N is even.

This result reduces the problem to N odd. The Hasse diagram of the powerset of S when N is odd looks like this (the particular case depicted is N = 5):

We name the layers of the diagram S₀,...,S_N. S_i consists of the subsets of S with cardinality i. We have |S_i| = C(N,i). A permutation covers exactly one element of each S_i. Similarly, a tuple τ of n non-repeating elements covers exactly one element of each of S₀,...,S_n. So, a minimal tuple cover of S₀,...,S_n can be proved to have as many elements as the largest layer covered. The next result shows how to extend a minimal tuple cover of S₀,...,S_{(N − 1)/2} , which has cardinality C(N,(N − 1)/2) = C(N,floor(N/2)) and spreads over the bottom half of the powerset of S, to a minimal permutation cover of S.

Theorem. Assume that N is odd and set M = (N − 1)/2. Let Τ be a minimal set of M-tuples of non-repeating elements covering S₀ U ... U S_M, and d : S_M → S_M a bijection with X ∩ d(X) = Ø for all X in S_M. The set Σ defined as

Σ = { τ·a·reverse(τ') : τ,τ' belong to Τ, range(τ') = d(range(τ)), a = S − range(τ) − range(τ')}

is a minimal permutation cover of S.

Proof. We see first that to each τ in Τ there corresponds exactly one permutation σ_τ of the form τ·a·reverse(τ') described above: since Τ is minimal each element of S_M is covered by one and only one element of Τ; so, for each τ there is exactly one τ' covering d(range(τ)). We prove now that Σ covers S: let X be a subset of S; if |X| ≤ M, X is covered by some τ in Τ and hence also by the associated σ_τ; if |X| > M, the set Y = S − X has |Y| ≤ M and is thus covered by some τ' in Τ; as we have seen, τ' univocally determines a permutation σ = τ·a·reverse(τ'), and σ obviously covers X, as all the elements of Y are packed at the tail of the permutation. Finally, Σ is minimal, since |Σ|= |Τ| and we saw before that |Τ| = C(N,floor(N/2)).

The mapping τ → σ_τ just defined can be described in a more algorithmic fashion as follows:

1. Find the τ' in Τ covering d(range(τ)).
2. Let a be the only element of S not present in τ nor τ'.
3. σ_τ := τ·a·reverse(τ').

Note that the last theorem extends easily to N even: in this case, the permutations have the form τ·reverse(τ'), i.e. there is no middle element a. However, it is more efficient to reduce the case N even to N − 1 using the first theorem of this entry.

Now we are left with the tasks of designing an algorithm to generate a tuple set Τ covering S₀ U ... U S_M and finding a suitable bijection d : S_M → S_M.

Profiling stable_vector

The two random access containers of the C++ standard library, std::vector and std::deque, have the same big-O complexity as stable_vector for the following operations:

• push_back: amortized constant
• middle insert: O(n)
• operator[]: constant

Yet the differences in actual performance vary wildly. I have written a profile program that measures the time taken by the three containers at these operations for two different value types: int and a "heavy" user defined type bigobj holding an int and an std::string. The program was built with release mode settings with MSVC++ 8.0 and GNU GCC 3.4.4 for Cygwin/MinGW. Resulting times are summarized in the following table: values are normalized to the minimum among the three containers.

MSVC++ 8.0
	int			bigobj
	std:: vector	std:: deque	stable_ vector	std:: vector	std:: deque	stable_ vector
push_back	1.00	4.06	21.37	1.00	1.09	1.26
insert	1.00	4.24	5.29	1.50	1.73	1.00
operator[]	1.00	3.35	1.01	1.00	3.27	1.09
GNU GCC 3.4.4
	int			bigobj
	std:: vector	std:: deque	stable_ vector	std:: vector	std:: deque	stable_ vector
push_back	1.09	1.00	91.57	1.08	1.00	1.14
insert	1.00	1.30	5.17	21.38	21.36	1.00
operator[]	1.00	41.04	1.11	1.00	81.68	2.03

For small objects like int, std::vector is, as expected, the fastest or very close to the fastest at every operation. push_back takes much longer for stable_vector than std::deque presumably because the latter allocates element chunks thus amortizing allocation time whereas stable_vector performs an allocation for every new node. The poor performance of stable_vector at insert can be attributed to the operation of adjustment of "up" pointers with each insertion operation, which is considerably slower than the simple int copying incurred by the other two containers. Finally, note that random access is very slow for std::deque because it involves some non-trivial arithmetical calculations, whereas std::vector and stable_vector only perform simple pointer offsets and indirections.

When storing heavy objects with expensive copy, the situation changes somewhat. The fact that stable_vector does not internally copy elements upon resizing or shrinking improves its relative performance with respect to the other two containers at push_back, and specially at insert, where stable_vector is the fastest.

This basic analysis suggests that the main performance handicap of stable_vector stems from the fact that it is a node-based container, as opposed to the chunk-based nature of std::vector and std::deque. This drawback might be alleviated by the use of burst-allocation, as proposed by Ion Gaztañaga.

Too powerful to evolve

Paragraph 1.4.8 of the C++ standard (draft copy) states that

A conforming implementation may have extensions (including additional library functions), provided they do not alter the behavior of any well-formed program.

It turns out that, strictly speaking, this unexpectedly bans many possible extensions an implementation of the C++ standard library might provide; C++ is such a powerful beast that a well-formed program might be made to depend on the non-existence of certain entities.

Function and function templates. The following program

‎#include <algorithm>
‎
‎using namespace std;
‎
‎int any_of(int count,int n1,...){/*...*/}
‎
‎int main()
‎{
‎  int n=any_of(2,1023,233);
‎}
‎

is valid C++03, but will fail with the upcoming C++0x revision of the standard, as this includes a function template any_of within <algorithm>:

‎template <class InputIterator, class Predicate>
‎bool any_of(InputIterator first, InputIterator last, Predicate pred);

that takes precedence over the user defined any_of due to the using namespace std directive.

Classes and class templates. Similarly, this C++03 valid program

‎#include <functional>
‎
‎using namespace std;
‎
‎template<typename T>
‎struct hash
‎{
‎  size_t operator()(const T& t){/*...*/}
‎};
‎
‎int main()
‎{
‎  hash<int>   h;
‎  size_t s=h(983265);
‎}
‎

will fail with C++0x due to the presence of an homonym hash in <functional>.

Member functions. The previous situations can be avoided if non-standard extensions are declared in separate headers or belong to a namespace other than std. These measures cannot be taken, however, when we are adding members to a standard class. The following is a totally artificial yet valid C++03 program:

‎#include <vector>
‎
‎template<class Vector>
‎int foo(char x){/*...*/}
‎
‎template <typename T,void (T::*)()> struct mfp{};
‎
‎template<class Vector>
‎void* foo(int x,mfp<Vector,&Vector::shrink_to_fit>* =0){/*...*/}
‎
‎int main()
‎{
‎  int x=foo<std::vector<int> >(0);
‎}

The so-called SFINAE rule prevents the second overload of foo to be selected because vector has no member function called shrink_to_fit; but it does in C++0x, rendering the program invalid (the second foo return type is not convertible to int).

Of course this is not a serious objection to the C++ standard text: 1.4.8 could always be rephrased to restrict it to reasonable well-formed programs, for some definition of "reasonable". But it can be instructive to reflect on how C++ has become so powerful (some would say complex) that such devious tricks can emerge (and, in some cases, be benefited from).

A causality calculus

Let us design a first-order calculus including causality as non-truth-functional connective for which causality semantics is defined at the same level as the rest of the (truth-functional) connectives, according to the philosophical position stated in a previous entry. We assume we are given an infinite set of variables V and a set R of predicate symbols with associated arities.

Propositional constants: F (falsehood).

Connectives: → (only if), > (causal implication).

Quantifiers: V (for all).

Axioms and rules of inference: the usual ones for standard first-order calculus plus the following axiom schemas dealing with causality:

(C₁) p > q, q > r → p > r

(C₂) (p > p) → F

(C₃) p > q → (p and q)

(C₄) p > r → (p or q) > r

(C₅) p > (q and r) → p > q

These axioms deserve some comment: C₁ states the usual transitivity of causation, while C₂ says that no event causes itself; C₃ allows us to speak about causation only among events actually taking place, which makes this a "realist" semantics. C₄ and C₅ translate some usual properties of material implication to causal implication.

Semantics: a valuation v specifies several mappings:

• From V to some set U.
• From each n-ary predicate in R to some n-ary relation in U.
• From each formula to the set {F,T}.

and obeys the following rules:

• v(F) = F.
• v(φ → ψ) = T iff v(φ) = F or v(ψ) = T.
• v(R(t₁,...,t_n)) = T iff (v(t₁),...,v(t_n)) is in v(R).
• v(Vx φ) = T iff v'(φ) = T for every valuation v' identical to v except possibly at x.
• The relation on formulas of the calculus defined by v(φ > ψ) = T is consistent with axiom schemas C₁,..., C₅. In particular, this implies that the relation thus defined is a strict partial order.
  

As usual, a statement is valid if it is true for any valuation. It is easy to see that there are valuations with the properties described above: just take any valuation for standard first-order predicate calculus and augment it with v(φ > ψ) = F for all φ, ψ (we may call this a Humean valuation).

Introducing stable_vector

We present stable_vector, a fully STL-compliant stable container that provides most of the features of std::vector except element contiguity. The underlying data structure has been discussed in a prior entry.

• stable_vector.hpp. The code uses Boost.
• test_stable_vector.cpp: Test suite for stable_vector.
  

In the following we are using the terminology of the C++98 standard.

General properties. stable_vector satisfies all the requirements of a container, a reversible container and a sequence and provides all the optional operations present in std::vector. Like std::vector, iterators are random access. stable_vector does not provide element contiguity; in exchange for this absence, the container is stable, i.e. references and iterators to an element of a stable_vector remain valid as long as the element is not erased, and an iterator that has been assigned the return value of end() always remain valid until the destruction of the associated stable_vector.

Operation complexity. The big-O complexities of stable_vector operations match exactly those of std::vector. In general, insertion/deletion is constant time at the end of the sequence and linear elsewhere. Unlike std::vector, stable_vector does not internally perform any value_type destruction, copy or assignment operations other than those exactly corresponding to the insertion of new elements or deletion of stored elements, which can sometimes compensate in terms of performance for the extra burden of doing more pointer manipulation and an additional allocation per element.

Exception safety. (according to Abrahams' terminology) As stable_vector does not internally copy elements around, some operations provide stronger exception safety guarantees than in std::vector:

operation	exception safety for std::vector<T>	exception safety for stable_vector<T>
insert	strong unless copy or assignment of T throw (basic)	strong
erase	no-throw unless copy or assignment of T throw (basic)	no-throw

Memory overhead. The C++ standard does not specifiy requirements on memory consumption, but virtually any implementation of std::vector has the same behavior wih respect to memory usage: the memory allocated by a vector v with n elements of type T is

m_v = c·e,

where c is v.capacity() and e is sizeof(T). c can be as low as n if the user has explicitly reserved the exact capacity required; otherwise, the average value c for a growing vector oscillates between 1.25·n and 1.5·n for typical resizing policies. For stable_vector, the memory usage is

m_sv = (c + 1)p + (n + 1)(e + p),

where p is the size of a pointer. We have c + 1 and n + 1 rather than c and n because a dummy node is needed at the end of the sequence. If we call f the capacity to size ratio c/n and assume that n is large enough, we have that

m_sv/m_v ≈ (fp + e + p)/fe.

So, stable_vector uses less memory than std::vector only when e > p and the capacity to size ratio exceeds a given threshold:

m_sv < m_v ↔ f > (e + p)/(e − p). (provided e > p)

This threshold approaches typical values of f below 1.5 when e > 5p; in a 32-bit architecture, when e > 20 bytes.

Summary. stable_vector is a drop-in replacement for std::vector providing stability of references and iterators, in exchange for missing element contiguity and also some performance and memory overhead. When the element objects are expensive to move around, the performance overhead can turn into a net performance gain for stable_vector if many middle insertions or deletions are performed or if resizing is very frequent. Similarly, if the elements are large there are situations when the memory used by stable_vector can actually be less than required by std::vector.