#!/usr/bin/env dub
/+ dub.sdl:
name "gcd_target_queue_funnel"
platforms "osx"
targetPath "build"
+/
/**
* GCD — target queues: mutual exclusion without a lock, composed at run time.
*
* Every dispatch object has a *target queue*. A queue you create owns no
* threads; it is a lane that re-enqueues its work onto its target, and only the
* root queue at the bottom of the chain is backed by the kernel's workqueue.
* Retargeting several serial queues onto one serial queue therefore funnels
* them into a single execution context — the subsystem-wide mutual exclusion
* Apple recommends in place of a shared lock, with no lock ever taken.
*
* This program runs the same workload twice: three serial queues targeting the
* default root queue (free to run concurrently), and the same three retargeted
* onto one funnel queue. It measures the peak observed concurrency in each case
* and asserts that the funnelled run never exceeds one, and that a
* deliberately unsynchronised counter is exact under the funnel.
*
* Companion to the GCD deep-dive:
* see docs/research/async-io/gcd/index.md § "Target queues: the hierarchy is the design".
*
* Run with: `dub run --single target-queue-funnel.d`
*
* Portability: macOS only (`platforms "osx"`).
*/
module (module) gcd_target_queue_funnelGCD — target queues: mutual exclusion without a lock, composed at run time.
Every dispatch object has a target queue. A queue you create owns no
threads; it is a lane that re-enqueues its work onto its target, and only the
root queue at the bottom of the chain is backed by the kernel's workqueue.
Retargeting several serial queues onto one serial queue therefore funnels
them into a single execution context — the subsystem-wide mutual exclusion
Apple recommends in place of a shared lock, with no lock ever taken.
This program runs the same workload twice: three serial queues targeting the
default root queue (free to run concurrently), and the same three retargeted
onto one funnel queue. It measures the peak observed concurrency in each case
and asserts that the funnelled run never exceeds one, and that a
deliberately unsynchronised counter is exact under the funnel.
Companion to the GCD deep-dive:
see docs/research/async-io/gcd/index.md § "Target queues: the hierarchy is the design".
Run with: dub run --single target-queue-funnel.d
Portability
macOS only (platforms "osx").
gcd_target_queue_funnel;
import (package) corecore.(module) core.atomicThe atomic module provides basic support for lock-free
concurrent programming.
Use the -preview=nosharedaccess compiler flag to detect
unsafe individual read or write operations on shared data.
Source
core/atomic.d
Examples
int y = 2;
shared int x = y; // OK
//x++; // read modify write error
x.atomicOp!"+="(1); // OK
//y = x; // read error with preview flag
y = x.atomicLoad(); // OK
assert(y == 3);
//x = 5; // write error with preview flag
x.atomicStore(5); // OK
assert(x.atomicLoad() == 5);
atomic : (alias template) gcd_target_queue_funnel.atomicLoad = core.atomic.atomicLoad(MemoryOrder ms = MemoryOrder.seq, T)(auto ref return scope const T val) if (!is(T == shared(U), U) && !is(T == shared(inout(U)), U) && !is(T == shared(const(U)), U))Loads 'val' from memory and returns it. The memory barrier specified
by 'ms' is applied to the operation, which is fully sequenced by
default. Valid memory orders are MemoryOrder.raw, MemoryOrder.acq,
and MemoryOrder.seq.
atomicLoad, (alias template) gcd_target_queue_funnel.atomicOp = core.atomic.atomicOp(string op, T, V1)(ref shared T val, V1 mod) if (__traits(compiles, mixin("*cast(T*)&val" ~ op ~ "mod")))Performs the binary operation 'op' on val using 'mod' as the modifier.
atomicOp, (alias template) gcd_target_queue_funnel.atomicStore = core.atomic.atomicStore(MemoryOrder ms = MemoryOrder.seq, T, V)(ref T val, V newval) if (!is(T == shared) && !is(V == shared))Writes 'newval' into 'val'. The memory barrier specified by 'ms' is
applied to the operation, which is fully sequenced by default.
Valid memory orders are MemoryOrder.raw, MemoryOrder.rel, and
MemoryOrder.seq.
atomicStore;
import (package) corecore.(package) core.stdcstdc.(module) core.stdc.stdintD header file for C99.
pubs.opengroup.org/onlinepubs/009695399/basedefs/stdint.h.html, stdint.h
Source
core/stdc/stdint.d
stdint : intptr_t, uintptr_t;
import (package) stdstd.(module) std.stdioCategory Symbols File handles _popen File isFileHandle openNetwork stderr stdin stdout Reading chunks lines readf readfln readln Writing toFile write writef writefln writeln Misc KeepTerminator LockType StdioException
Standard I/O functions that extend core.stdc.stdio. core.stdc.stdio
is publically imported when importing std.stdio.
There are three layers of I/O:
The lowest layer is the operating system layer. The two main schemes are Windows and Posix.
C's stdio.h which unifies the two operating system schemes.
std.stdio, this module, unifies the various stdio.h implementations into
a high level package for D programs.
Source
std/stdio.d
stdio : (alias template) gcd_target_queue_funnel.writefln = std.stdio.writefln(alias fmt, A...)(A args) if (isSomeString!(typeof(fmt)))Equivalent to writef(fmt, args, '\n').
writefln, (alias template) gcd_target_queue_funnel.writeln = std.stdio.writeln(T...)(T args)Equivalent to write(args, '\n'). Calling writeln without
arguments is valid and just prints a newline to the standard
output.
Example
Reads stdin and writes it to stdout with an argument
counter.
import std.stdio;
void main()
{
string line;
for (size_t count = 0; (line = readln) !is null; count++)
{
writeln("Input ", count, ": ", line);
}
}
writeln;
alias (alias) gcd_target_queue_funnel.dispatch_queue_t = void*dispatch_queue_t = void*;
alias (alias) gcd_target_queue_funnel.dispatch_group_t = void*dispatch_group_t = void*;
alias (alias) gcd_target_queue_funnel.dispatch_function_t = extern (C) void function(void*) nothrowdispatch_function_t = extern (C) void function(void*) nothrow;
extern (C) nothrow @nogc
{
(alias) gcd_target_queue_funnel.dispatch_queue_t = void*dispatch_queue_t void* gcd_target_queue_funnel.dispatch_queue_create(const(char)* label, void* attr) nothrow @nogcdispatch_queue_create(const(char)* (parameter) const(char)* labellabel, void* (parameter) void* attrattr);
(alias) gcd_target_queue_funnel.dispatch_queue_t = void*dispatch_queue_t void* gcd_target_queue_funnel.dispatch_get_global_queue(long identifier, ulong flags) nothrow @nogcdispatch_get_global_queue(intptr_t (parameter) long identifieridentifier, uintptr_t (parameter) ulong flagsflags);
void void gcd_target_queue_funnel.dispatch_set_target_queue(void* object, void* queue) nothrow @nogcdispatch_set_target_queue(void* (parameter) void* objectobject, (alias) gcd_target_queue_funnel.dispatch_queue_t = void*dispatch_queue_t (parameter) void* queuequeue);
(alias) gcd_target_queue_funnel.dispatch_group_t = void*dispatch_group_t void* gcd_target_queue_funnel.dispatch_group_create() nothrow @nogcdispatch_group_create();
void void gcd_target_queue_funnel.dispatch_group_async_f(void* group, void* queue, void* context, extern (C) void function(void*) nothrow work) nothrow @nogcdispatch_group_async_f((alias) gcd_target_queue_funnel.dispatch_group_t = void*dispatch_group_t (parameter) void* groupgroup, (alias) gcd_target_queue_funnel.dispatch_queue_t = void*dispatch_queue_t (parameter) void* queuequeue,
void* (parameter) void* contextcontext, (alias) gcd_target_queue_funnel.dispatch_function_t = extern (C) void function(void*) nothrowdispatch_function_t (parameter) extern (C) void function(void*) nothrow workwork);
long long gcd_target_queue_funnel.dispatch_group_wait(void* group, ulong timeout) nothrow @nogcdispatch_group_wait((alias) gcd_target_queue_funnel.dispatch_group_t = void*dispatch_group_t (parameter) void* groupgroup, ulong (parameter) ulong timeouttimeout);
void void gcd_target_queue_funnel.dispatch_release(void* object) nothrow @nogcdispatch_release(void* (parameter) void* objectobject);
}
enum (constant) ulong gcd_target_queue_funnel.DISPATCH_TIME_FOREVER = 18446744073709551615LUDISPATCH_TIME_FOREVER = ~0UL;
enum (constant) int gcd_target_queue_funnel.QOS_CLASS_DEFAULT = 21QOS_CLASS_DEFAULT = 0x15;
enum (constant) int gcd_target_queue_funnel.laneCount = 3laneCount = 3;
enum (constant) int gcd_target_queue_funnel.itemsPerLane = 200itemsPerLane = 200;
struct (struct) gcd_target_queue_funnel.RunRun
{
shared int (field) shared(int) gcd_target_queue_funnel.Run.inFlightinFlight;
shared int (field) shared(int) gcd_target_queue_funnel.Run.peakInFlightpeakInFlight;
/// Deliberately not atomic: it is exact only if the work is serialised.
int (field) int gcd_target_queue_funnel.Run.unguardedCounterDeliberately not atomic: it is exact only if the work is serialised.
unguardedCounter;
}
__gshared (struct) gcd_target_queue_funnel.RunRun (__gshared global) gcd_target_queue_funnel.Run gcd_target_queue_funnel.runrun;
extern (C) void void gcd_target_queue_funnel.workItem(void* context) nothrowworkItem(void* (parameter) void* contextcontext) nothrow
{
const (local variable) const(int) nownow = int core.atomic.atomicOp!("+=", int, int)(ref shared(int) val, int mod) pure nothrow @nogc @safePerforms the binary operation 'op' on val using 'mod' as the modifier.
atomicOp!"+="((__gshared global) gcd_target_queue_funnel.Run gcd_target_queue_funnel.runrun.(field) shared(int) gcd_target_queue_funnel.Run.inFlightinFlight, 1);
// Track the high-water mark of simultaneous executions.
for (;;)
{
const (local variable) const(int) peakpeak = int core.atomic.atomicLoad!(MemoryOrder.seq, int)(ref return scope shared(const(int)) val) pure nothrow @nogc @trustedLoads 'val' from memory and returns it. The memory barrier specified
by 'ms' is applied to the operation, which is fully sequenced by
default. Valid memory orders are MemoryOrder.raw, MemoryOrder.acq,
and MemoryOrder.seq.
atomicLoad((__gshared global) gcd_target_queue_funnel.Run gcd_target_queue_funnel.runrun.(field) shared(int) gcd_target_queue_funnel.Run.peakInFlightpeakInFlight);
if ((local variable) const(int) nownow <= (local variable) const(int) peakpeak)
break;
import (package) corecore.(module) core.atomicThe atomic module provides basic support for lock-free
concurrent programming.
Use the -preview=nosharedaccess compiler flag to detect
unsafe individual read or write operations on shared data.
Source
core/atomic.d
Examples
int y = 2;
shared int x = y; // OK
//x++; // read modify write error
x.atomicOp!"+="(1); // OK
//y = x; // read error with preview flag
y = x.atomicLoad(); // OK
assert(y == 3);
//x = 5; // write error with preview flag
x.atomicStore(5); // OK
assert(x.atomicLoad() == 5);
atomic : (alias template) cas = core.atomic.cas(MemoryOrder succ = MemoryOrder.seq, MemoryOrder fail = MemoryOrder.seq)Performs either compare-and-set or compare-and-swap (or exchange).
There are two categories of overloads in this template:
The first category does a simple compare-and-set.
The comparison value (ifThis) is treated as an rvalue.
The second category does a compare-and-swap (a.k.a. compare-and-exchange),
and expects ifThis to be a pointer type, where the previous value
of here will be written.
This operation is both lock-free and atomic.
Params:
here = The address of the destination variable.
writeThis = The value to store.
ifThis = The comparison value.
Returns:
true if the store occurred, false if not.
cas;
if (bool core.atomic.cas!().cas!(int, const(int), const(int))(shared(int)* here, const(int) ifThis, const(int) writeThis) pure nothrow @nogc @trustedPerforms either compare-and-set or compare-and-swap (or exchange).
There are two categories of overloads in this template:
The first category does a simple compare-and-set.
The comparison value (ifThis) is treated as an rvalue.
The second category does a compare-and-swap (a.k.a. compare-and-exchange),
and expects ifThis to be a pointer type, where the previous value
of here will be written.
This operation is both lock-free and atomic.
cas(&(__gshared global) gcd_target_queue_funnel.Run gcd_target_queue_funnel.runrun.(field) shared(int) gcd_target_queue_funnel.Run.peakInFlightpeakInFlight, (local variable) const(int) peakpeak, (local variable) const(int) nownow))
break;
}
// A read-modify-write with no synchronisation of its own. Under a funnel it
// is exact; run concurrently it loses updates.
const (local variable) const(int) scratchscratch = (__gshared global) gcd_target_queue_funnel.Run gcd_target_queue_funnel.runrun.(field) int gcd_target_queue_funnel.Run.unguardedCounterDeliberately not atomic: it is exact only if the work is serialised.
unguardedCounter;
(__gshared global) gcd_target_queue_funnel.Run gcd_target_queue_funnel.runrun.(field) int gcd_target_queue_funnel.Run.unguardedCounterDeliberately not atomic: it is exact only if the work is serialised.
unguardedCounter = (local variable) const(int) scratchscratch + 1;
int core.atomic.atomicOp!("-=", int, int)(ref shared(int) val, int mod) pure nothrow @nogc @safePerforms the binary operation 'op' on val using 'mod' as the modifier.
atomicOp!"-="((__gshared global) gcd_target_queue_funnel.Run gcd_target_queue_funnel.runrun.(field) shared(int) gcd_target_queue_funnel.Run.inFlightinFlight, 1);
}
/// Runs `laneCount * itemsPerLane` items across `lanes`, returning the peak
/// observed concurrency and the value the unguarded counter reached.
auto gcd_target_queue_funnel.measure.Result gcd_target_queue_funnel.measure(void*[] lanes) nothrow @nogc @systemRuns laneCount * itemsPerLane items across lanes, returning the peak
observed concurrency and the value the unguarded counter reached.
measure((alias) gcd_target_queue_funnel.dispatch_queue_t = void*dispatch_queue_t[] (parameter) void*[] laneslanes)
{
void core.atomic.atomicStore!(MemoryOrder.seq, int, int)(ref shared(int) val, int newval) pure nothrow @nogc @trustedWrites 'newval' into 'val'. The memory barrier specified by 'ms' is
applied to the operation, which is fully sequenced by default.
Valid memory orders are MemoryOrder.raw, MemoryOrder.rel, and
MemoryOrder.seq.
atomicStore((__gshared global) gcd_target_queue_funnel.Run gcd_target_queue_funnel.runrun.(field) shared(int) gcd_target_queue_funnel.Run.inFlightinFlight, 0);
void core.atomic.atomicStore!(MemoryOrder.seq, int, int)(ref shared(int) val, int newval) pure nothrow @nogc @trustedWrites 'newval' into 'val'. The memory barrier specified by 'ms' is
applied to the operation, which is fully sequenced by default.
Valid memory orders are MemoryOrder.raw, MemoryOrder.rel, and
MemoryOrder.seq.
atomicStore((__gshared global) gcd_target_queue_funnel.Run gcd_target_queue_funnel.runrun.(field) shared(int) gcd_target_queue_funnel.Run.peakInFlightpeakInFlight, 0);
(__gshared global) gcd_target_queue_funnel.Run gcd_target_queue_funnel.runrun.(field) int gcd_target_queue_funnel.Run.unguardedCounterDeliberately not atomic: it is exact only if the work is serialised.
unguardedCounter = 0;
auto (local variable) void* groupgroup = void* gcd_target_queue_funnel.dispatch_group_create() nothrow @nogcdispatch_group_create();
scope (exit)
void gcd_target_queue_funnel.dispatch_release(void* object) nothrow @nogcdispatch_release((local variable) void* groupgroup);
foreach ((local variable) int itemitem; 0 .. (constant) int gcd_target_queue_funnel.itemsPerLane = 200itemsPerLane)
foreach ((parameter) void* lanelane; (parameter) void*[] laneslanes)
void gcd_target_queue_funnel.dispatch_group_async_f(void* group, void* queue, void* context, extern (C) void function(void*) nothrow work) nothrow @nogcdispatch_group_async_f((local variable) void* groupgroup, (local variable) void* lanelane, null, &void gcd_target_queue_funnel.workItem(void* context) nothrowworkItem);
long gcd_target_queue_funnel.dispatch_group_wait(void* group, ulong timeout) nothrow @nogcdispatch_group_wait((local variable) void* groupgroup, (constant) ulong gcd_target_queue_funnel.DISPATCH_TIME_FOREVER = 18446744073709551615LUDISPATCH_TIME_FOREVER);
struct (struct) gcd_target_queue_funnel.measure.ResultResult
{
int (field) int gcd_target_queue_funnel.measure.Result.peakpeak;
int (field) int gcd_target_queue_funnel.measure.Result.countercounter;
}
return (struct) gcd_target_queue_funnel.measure.ResultResult(int core.atomic.atomicLoad!(MemoryOrder.seq, int)(ref return scope shared(const(int)) val) pure nothrow @nogc @trustedLoads 'val' from memory and returns it. The memory barrier specified
by 'ms' is applied to the operation, which is fully sequenced by
default. Valid memory orders are MemoryOrder.raw, MemoryOrder.acq,
and MemoryOrder.seq.
atomicLoad((__gshared global) gcd_target_queue_funnel.Run gcd_target_queue_funnel.runrun.(field) shared(int) gcd_target_queue_funnel.Run.peakInFlightpeakInFlight), (__gshared global) gcd_target_queue_funnel.Run gcd_target_queue_funnel.runrun.(field) int gcd_target_queue_funnel.Run.unguardedCounterDeliberately not atomic: it is exact only if the work is serialised.
unguardedCounter);
}
int int D main()main()
{
(alias) gcd_target_queue_funnel.dispatch_queue_t = void*dispatch_queue_t[(constant) int gcd_target_queue_funnel.laneCount = 3laneCount] (local variable) void*[3] laneslanes;
static immutable (alias) object.string = stringstring[(constant) int gcd_target_queue_funnel.laneCount = 3laneCount] (immutable global) immutable(string[3]) gcd_target_queue_funnel.main.labelslabels = [
"dev.sparkles.research.gcd.lane.0\0",
"dev.sparkles.research.gcd.lane.1\0",
"dev.sparkles.research.gcd.lane.2\0",
];
foreach ((parameter) ulong ii, ref (parameter) void* lanelane; (local variable) void*[3] laneslanes)
(local variable) void* lanelane = void* gcd_target_queue_funnel.dispatch_queue_create(const(char)* label, void* attr) nothrow @nogcdispatch_queue_create((immutable global) immutable(string[3]) gcd_target_queue_funnel.main.labelslabels[(local variable) ulong ii].(field) immutable(char)* immutable(string).ptrptr, null);
scope (exit)
foreach ((parameter) void* lanelane; (local variable) void*[3] laneslanes)
void gcd_target_queue_funnel.dispatch_release(void* object) nothrow @nogcdispatch_release((local variable) void* lanelane);
const (local variable) const(int) expectedexpected = (constant) int gcd_target_queue_funnel.laneCount = 3laneCount * (constant) int gcd_target_queue_funnel.itemsPerLane = 200itemsPerLane;
// 1. Default targeting: each lane is serial with respect to itself, but the
// three lanes reach the root queue independently.
const (local variable) const(gcd_target_queue_funnel.measure.Result) independentindependent = gcd_target_queue_funnel.measure.Result gcd_target_queue_funnel.measure(void*[] lanes) nothrow @nogc @systemRuns laneCount * itemsPerLane items across lanes, returning the peak
observed concurrency and the value the unguarded counter reached.
measure((local variable) void*[3] laneslanes[]);
void std.stdio.writefln!(char, const(int), const(int), const(int))(in char[] fmt, const(int) __param_1, const(int) __param_2, const(int) __param_3) @safeEquivalent to writef(fmt, args, '\n').
writefln("three independent serial queues: peak concurrency = %d, counter = %d/%d",
(local variable) const(gcd_target_queue_funnel.measure.Result) independentindependent.(field) int gcd_target_queue_funnel.measure.Result.peakpeak, (local variable) const(gcd_target_queue_funnel.measure.Result) independentindependent.(field) int gcd_target_queue_funnel.measure.Result.countercounter, (local variable) const(int) expectedexpected);
// 2. Funnel them: one serial queue becomes the target of all three.
auto (local variable) void* funnelfunnel = void* gcd_target_queue_funnel.dispatch_queue_create(const(char)* label, void* attr) nothrow @nogcdispatch_queue_create("dev.sparkles.research.gcd.funnel", null);
scope (exit)
void gcd_target_queue_funnel.dispatch_release(void* object) nothrow @nogcdispatch_release((local variable) void* funnelfunnel);
void gcd_target_queue_funnel.dispatch_set_target_queue(void* object, void* queue) nothrow @nogcdispatch_set_target_queue((local variable) void* funnelfunnel, void* gcd_target_queue_funnel.dispatch_get_global_queue(long identifier, ulong flags) nothrow @nogcdispatch_get_global_queue((constant) int gcd_target_queue_funnel.QOS_CLASS_DEFAULT = 21QOS_CLASS_DEFAULT, 0));
foreach ((parameter) void* lanelane; (local variable) void*[3] laneslanes)
void gcd_target_queue_funnel.dispatch_set_target_queue(void* object, void* queue) nothrow @nogcdispatch_set_target_queue((local variable) void* lanelane, (local variable) void* funnelfunnel);
const (local variable) const(gcd_target_queue_funnel.measure.Result) funnelledfunnelled = gcd_target_queue_funnel.measure.Result gcd_target_queue_funnel.measure(void*[] lanes) nothrow @nogc @systemRuns laneCount * itemsPerLane items across lanes, returning the peak
observed concurrency and the value the unguarded counter reached.
measure((local variable) void*[3] laneslanes[]);
void std.stdio.writefln!(char, const(int), const(int), const(int))(in char[] fmt, const(int) __param_1, const(int) __param_2, const(int) __param_3) @safeEquivalent to writef(fmt, args, '\n').
writefln("the same three, retargeted to one: peak concurrency = %d, counter = %d/%d",
(local variable) const(gcd_target_queue_funnel.measure.Result) funnelledfunnelled.(field) int gcd_target_queue_funnel.measure.Result.peakpeak, (local variable) const(gcd_target_queue_funnel.measure.Result) funnelledfunnelled.(field) int gcd_target_queue_funnel.measure.Result.countercounter, (local variable) const(int) expectedexpected);
assert((local variable) const(gcd_target_queue_funnel.measure.Result) funnelledfunnelled.(field) int gcd_target_queue_funnel.measure.Result.peakpeak == 1, "the funnel queue did not serialise its lanes");
assert((local variable) const(gcd_target_queue_funnel.measure.Result) funnelledfunnelled.(field) int gcd_target_queue_funnel.measure.Result.countercounter == (local variable) const(int) expectedexpected, "an unsynchronised counter lost updates under the funnel");
assert((local variable) const(gcd_target_queue_funnel.measure.Result) independentindependent.(field) int gcd_target_queue_funnel.measure.Result.peakpeak >= 1, "no work ran");
void std.stdio.writeln!()() @safeEquivalent to write(args, '\n'). Calling writeln without
arguments is valid and just prints a newline to the standard
output.
Example
Reads stdin and writes it to stdout with an argument
counter.
import std.stdio;
void main()
{
string line;
for (size_t count = 0; (line = readln) !is null; count++)
{
writeln("Input ", count, ": ", line);
}
}
writeln();
if ((local variable) const(gcd_target_queue_funnel.measure.Result) independentindependent.(field) int gcd_target_queue_funnel.measure.Result.peakpeak > (local variable) const(gcd_target_queue_funnel.measure.Result) funnelledfunnelled.(field) int gcd_target_queue_funnel.measure.Result.peakpeak)
void std.stdio.writeln!string(string __param_0) @safeEquivalent to write(args, '\n'). Calling writeln without
arguments is valid and just prints a newline to the standard
output.
Example
Reads stdin and writes it to stdout with an argument
counter.
import std.stdio;
void main()
{
string line;
for (size_t count = 0; (line = readln) !is null; count++)
{
writeln("Input ", count, ": ", line);
}
}
writeln("retargeting alone converted three concurrent lanes into one serial context");
else
void std.stdio.writeln!string(string __param_0) @safeEquivalent to write(args, '\n'). Calling writeln without
arguments is valid and just prints a newline to the standard
output.
Example
Reads stdin and writes it to stdout with an argument
counter.
import std.stdio;
void main()
{
string line;
for (size_t count = 0; (line = readln) !is null; count++)
{
writeln("Input ", count, ": ", line);
}
}
writeln("this host never overlapped the independent lanes; the funnel guarantee still holds");
return 0;
}