sparkie
Btrees are O(log n) random access, O(log n) cons and use O(log n) excess space.
Unrolled linked lists are still O(n) random access because we ignore the constant factor of block size. They also use O(n) excess space for pointers, but have O(1) cons.
RAOTS are O(1) random access, O(1) amortized cons [O(√n) worse case], and use O(√n) excess space.
RAOTS is basically a tree of depth 1. The root is an "index block" of pointers to data blocks which grow in size proportional to the square root of the data length (similar to Hashed Array Trees, but doesn't require restructuring on each power of 2). The index block has length ~√n.
The square root is an approximation - the structure grows in "superblocks" where each superblock has `~√n` blocks of size `~√n` The pattern is: [1x1, 1x2, 2x2, 2x4, 4x4, 4x8, 8x8, 8x16, 16x16, 16x32, ...] Even indexed superblocks double the data block size, odd indexed superblocks double the number of blocks per superblock. It doesn't use an actual `sqrt()` call uses but some bit tricks via `clz`.
A simpler trick, which has no single name but have been known as "segmented lists", is where the index block points to blocks increasing in size geometrically essentially like a dynamic array but where we don't need to `realloc`. The index block is length 1+log₂n and each index i points to a block of length 2⁽ⁱ⁻¹⁾. These have O(1) random access, O(1) amortized cons [O(n) worst case] and waste O(n) space [with constant factor of 1/2]. The random access is very efficient as it's only two dereferences and a few bit tricks:
index_block[bit_width(idx)][idx - bit_floor(idx)]
There's also Bagwell's VList[2] which is like a mashup of the "segmented list" and an unrolled list - the blocks grow geometrically in size, but still contain the pointer the the next block rather than them being in a separate index block.
[1]:https://cs.uwaterloo.ca/research/tr/1999/09/CS-99-09.pdf
* Everyone is quick to make judgement on something they don't know all the details of.
* There's not much agreement - mostly people disagreeing with each other.
* Everyone's opinion is important - they're smart so obviously, they're always right.
* Unrelated politics - my pet issue must be talked about.
* Anything is better - it's impossible for things to get worse.
* I disagree with this opinion so it must be a Russian bot.
Anyway, I wonder what will happen if you get together a bunch of intellectuals in government.
Both government and academia know how to navigate this well - by avoiding accountability.
map :: (a -> b) -> (t a -> t b) -- Functor
bind :: (a -> t b) -> (t a -> t b) -- Monad
cobind :: (t a -> b) -> (t a -> t b) -- Comonad
ap :: t (a -> b) -> (t a -> t b) -- Applicative
The "ordered computation" isn't unique to monads, it applies to all of these when you chain them. For monads particularly though, you can't begin the continuation until the previous result has been generated - whereas with a comonad, you can begin the continuation right away and extract the value afterwards (inside the continuation).
Can also think of it like a producer/consumer or push/pull thing. Monads push values into some type `t`, and comonads pull values out of `t`.
The naming of `return` is perhaps unfortunate as it gives the impression you're returning a value (done to make do-notation look like imperative code) - but monads don't return values. `return` produces a computation.
`coreturn` is usually called `extract`, which is better naming - it extracts a value from a computation.
The order of arguments is also unfortunate because it makes the above pattern less obvious - they're usually written as:
fmap :: f a -> (a -> b) -> f b
bind :: m a -> (a -> m b) -> m b
Should probably use MeCab, which parses this correctly.
(h . g . f) x
(f >>> g >>> h) x
x |> (f >>> g >>> h) typedef struct {
double value;
int error;
} maybe_double;
When you use a union containing an int and a double, the double has to be moved to a GP register, and back to the vector register when read as a double (via movq), so there's a small hidden cost compared to the former approach. Your `Result_double` is returned in `rax:rdx`.
There's a trick you can use to avoid this - keep the `double` in the vector register and move the `int` to the vector register instead - so you only pay the cost to move between GP and vector registers when there's an error but not otherwise. To do this, make the union use `__m64` instead of `int` - the whole union is then in a vector register, and the `Result_double` struct is returned in `rax:xmm0`, as with `maybe_double` struct.
typedef struct {
_Bool ok;
union {
double value;
__m64 error;
};
} Result_double;
On MSVC we could maybe get maximum efficiency by using NaN-boxing - store the error code in the signalling NaN space - eg, treat NaNs beginning 0x7FF1 as error codes.
typedef union {
int64_t _as_int;
double _as_double;
} Result_double;
#define Result_double_value(n) \
(Result_double){ ._as_double = (n) };
#define Result_double_error(errcode) \
(Result_double){ ._as_int = (0x7FF1000000000000ULL | (errcode)) }
#define Result_double_is_error(x) \
(((x)._as_int & 0x7FFF000000000000ULL) == 0x7FF1000000000000ULL)
#define Result_double_get_error(x) \
((x)._as_int & 0x0000FFFFFFFFFFFFULL)
#define Result_double_get_value(x) \
((x)._as_double)
Result_double x = strtod·or·error(s, NULL)
if (Result_double_is_error(x)) {
handle(Result_double_get_error(x));
return;
}
use(Result_double_get_value(x))
Eg:
typedef struct {
bool has_value;
int value;
} option_int_t;
option_int_t foo() {
if (somecond) return (option_int_t){ true, somevalue };
else return (option_int_t){ false };
}
bool bar(int *out) {
if (somecond) {
*out = somevalue;
return true;
}
return false;
}
On other compilers this isn't the case. MSVC only supports 64-bit returns and would use the stack for `option_int_t`. The caller allocates the space and an implicit pointer is passed in the first argument register (eg, `rcx`), and the same pointer is returned as the result.
There's no mainstream language with negation types, but a few good research languages with them, eg MLstruct.
[MLstruct]:https://github.com/hkust-taco/mlstruct
typedef struct {
int status;
float value;
} div_result_t;
div_result_t divide(float a, float b) {
if (b = 0.0) return (div_result_t){ E_DIVZERO };
return (div_result_t){ 0, a / b };
}
On MSVC: The caller allocates `sizeof(div_result_t)` on the stack, passes the the pointer to that space as an implicit first argument to `divide` in register x0/rcx. The function returns the same pointer as its result in x0/rax.
The latter is almost equivalent to you passing a pointer manually - but the compiler does it for you. In the former case, it's actually more efficient to use the struct as we don't even need to touch the stack - all arguments and returns are in registers (for structs up to two "eightbytes" - ie, 16-bytes).
IMO, if it intended to use automatic storage duration, and the size of the struct is small enough, returning by value is preferable - it performs better on SYSV, and basically automates what you would do manually on MSVC. If it is intended for manual storage duration, then yes, use pass and return by pointer explicitly.
> An integer may be converted to any pointer type. Except as previously specified, the result is implementation-defined, may not be correctly aligned, may not point to an entity of the referenced type, and can produce an indeterminate representation when stored into an object
The compiler may specify otherwise. GCC specifies that the pointer cast to integer back to pointer must point to the original object, else the behavior is undefined.
AFAIK, this was only an issue in some older CPUs and isn't a problem today.
32-bit `int` is still cheaper than 16-bits though, because 16-bit instructions require an operand size override prefix (0x66), or address size override prefix (0x67), or both. Technically, these aren't "16 bit prefixes" - if the machine was running in 16-bit protected mode, then you would need those prefixes to use 32-bit instructions and the non-prefixed ones would be 16-bit and thus cheaper, so `int` would be better as 16-bits in 16-bit protected mode - though this mode is essentially unused today, so for all intents and purposes the prefixes are used to issue 16-bit instructions and 16-bits is more expensive (in code size, i-cache usage, which may impact performance).
https://github.com/gcc-mirror/gcc/blob/master/gcc/ginclude/s...
There's a simpler way to define these types in newer versions of C which have `typeof`, we can take advantage of the fact that `sizeof()` always returns a `size_t`, `ptr - ptr` always returns a `ptrdiff_t`, and a literal L'c' has type `wchar_t`, etc.
typedef typeof(sizeof(0)) size_t;
typedef typeof(nullptr) nullptr_t;
typedef typeof((void*)0-(void*)0) ptrdiff_t;
typedef typeof(L'\0') wchar_t;
typedef typeof(u8'\0') char8_t;
typedef typeof(u'\0') char16_t;
typedef typeof(U'\0') char32_t;
A `thread_local`'s actual virtual address is not merely what the pointer contains - it's an offset from some other virtual address stored in the FS or GS register (on x86-64), which is swapped when you change thread. Casting the pointer to `intptr_t` does not retain the segment base address - only the offset. The pointer is not the absolute address.
If you dereference in another thread, it's the same offset, but from a different base address.
There may be other things besides segment registers on other architectures that also make it unsafe. The C standard makes no guarantee that you can safely dereference a pointer cast from `intptr_t`.
When amd64 was released, x86 was almost ubiquitous on desktops and ran the majority of servers - most of the software used by the world could continue being used. If AMD had not gone through this effort to make it backward compatible, it's likely IA64 would've won and we wouldn't have this debate. Hard to understate the importance of not breaking things.
If you were designing a greenfield 64-bit ISA, then yes, it might make sense to have `int` be 64-bits, but it was definitely not, and still is not a mistake that it's 32-bits on amd64.
On RISC-V for example, it's questionable. The RV32 ecosystem is tiny and almost irrelevant - if they decided to break things for RV64 it wouldn't be a big problem - probably better to fix any problems early rather than hold baggage to run software that never existed - though it's much easier to port software to RV64 if `int` is still 32-bits.
typedef unsigned __attribute__((mode(HI))) uint16_t;
typedef signed __attribute__((mode(SI))) int32_t;
The amd64 design could run most 32-bit code with minimal changes. All the 32-bit instructions had the same encoding, besides push/pop which instead acted on 64-bits. The 64-bit instructions were basically opt-in, though a few opcodes (0x40..0x4F) had to be deprecated for the REX prefix.
It isn't. `int` is at least as large as `short` and at least 16-bits. On modern systems `int` is still typically 32-bits whereas `size_t` is typically 64-bits. There's a `ssize_t` in POSIX for signed sizes.
> When people want the classic 4 byte data type they should choose long instead.
`long` is only at least 4 bytes, and at least as large as `int`. On MSVC (LLP64 data model) it's 4 bytes, but on SYSV (LP64 data model) it's 8 bytes. `long` should almost never be used if you actually want portable code today.
`int` is 32-bits and `long long` is 64-bits on both LP64 and LLP64. If you want portable code using the native integer types, these are the ones you should use, definitely not `long`.
On Intel 286 we had a 16-bit machine word and 24-bit addresses. A pointer wasn't just two machine words concatenated - the upper 8 bits were stored somewhere else - a segment register.
On modern machines we don't (usually) need to consider this because we have a single linear virtual address space, though the size is architecture dependant - usually above 40 bits and below 64. Most common size is 48-bits, but also up to 57-bits with 5 level paging enabled.
Either way we round up to 64-bits to store the pointer as one integer. C optionally provides types `intptr_t` and `uintptr_t`, which are integers large enough to hold the value of a pointer. Converting a pointer to `intptr_t` and back to the pointer type results in a pointer that compares equal to the original.
However, there is no guarantee that a pointer converted to `intptr_t` and back to a pointer can be dereferenced! It works most of the time because of our linear address space and non-use of segmentation, but segmentation can still be used - the FS and GS segment registers are still available on x86_64 and are commonly used for thread local storage. If you take a `thread_local T*`, convert it to `intptr_t`, and then convert it back to a `thread_local T*` on another thread and attempt to dereference it, then despite the pointers comparing equal, they dereference to different virtual addresses.
Integers tied to the size of a pointer would have been misguided. Pointers are not integers! (They just happen to use an integer in their representation).
Another one, `size_t` is supposed to represent the maximum size of any object. However, that's also not well-defined. The maximum object size on the Intel 256 would have been 16-bits, because that is all you can fit in a single segment.
On a modern machine, a `size_t` should really be 48-bits (4LP) or 57-bits (5LP), because we can't have an object larger than our maximum virtual address size - but `size_t` is typically 64-bits.
They're a proper superset of regular languages and a proper subset of deterministic context-free languages, but they retain many of the nice properties of regular languages that DCFLs don't - they're closed under intersection, union, concatenation, Kleene Star and reversal.
They can parse more languages that Regular Expressions (non PCRE), but fewer than deterministic CFG subsets like LL/LR. They're expressive enough to parse languages which have a regular tree structure like S-expressions, JSON, XHTML.
It's awkward to do get right because you need an indirect pointer whose address remains fixed, but points to another pointer which can change (and is volatile).
While it might be possible to make something like this lockless - it's much simpler to stick a mutex in the array header. When we access the array_segment we can take a lock to prevent some other thread reallocating mid-way through accessing.
There's probably a few improvements that could be made. In particular it doesn't handle use-after-free, so it's not thread safe w.r.t cleanup.
Examples would be eg, `string_view` or `ArraySegment`. They hold some offset relative to a base allocation, and when we index the string_view or ArraySegment we're indexing relative to that offset.
Segmentation isn't used. There's no separate registers to hold the bounds information in CHERI - the bounds are held in the pointer value, unlike for example, the now obsolete Intel MPX, which held bounds information in separate registers.
There's some similarity to segmentation because the CHERI pointer restricts which addresses can be accessed, but I wouldn't compare them to far pointers.
Most modern processors have a single linear virtual address space and don't use segmentation, and even where segment registers exist (eg, FS and GS on x86-64), they're only superficial "address spaces" - allocated sections of the process's linear virtual address space which could be accessed without segmentation registers if you knew the base address held in FS or GS.
GCC still supports `__seg_fs` and `__seg_gs`, which behave similar to `far` in the example on the wiki page, as the FS and GS segment registers are still valid in x86-64 and used for TLS. Clang uses attributes `address_space(257)` and `address_space(256)` for the same thing.
The `__based` pointer in MSVC exploits the addressing modes by pinning the base in eg: `[base+index*scale+displacement]`. It's unrelated to segmentation.
Conversely, the wealthiest are frequent flyers, are chauffeured about in SUVs and rarely walk. They have everything they'll ever need and don't concern themselves about running the AC or heating.
They're preaching to the poor guy about what he needs to do to stop climate change.
Even if the poor guy wanted to care, he can't do much, but the people who claim to care could do a lot more, if they really did care.
The media circus tries to put the blame on the poor, while ignoring the emissions of the celebrities and treating them as royalty. Is it any wonder most people simply don't care?
If the media cared, they would be making villains of the celebrities and idols of the poor.
`thread_local` is an example of a "relative pointer" though. Instructions to access the thread local are prefixed with `fs:` or `gs:`, and point relative to the address in the respective segment register.