Why does Deque.at return T instead of ?T

Explain
1

I understand that the implementation for zig 0.16.0 is

pub fn at(deque: *const Self, index: usize) T {
    assert(index < deque.len);
    return deque.buffer[deque.bufferIndex(index)];
}

I would have expected to be something like this.

pub fn at(deque: *const Self, index: usize) ?T {
    if(index >= deque.len) return null
    return deque.buffer[deque.bufferIndex(index)];
}

Is there a reason why the function does not return an optional? the optional would be better because it gives you the static check instead of a runtime crash.

Since this is my first question about the source code, i thought id ask first before i suggest changes.

1 Like
2

My guess is that since the caller already has access to the deque’s length, they figure it’s up to the caller to bounds-check the index and simply assert that the caller did.
This enables cases where, for better performance, when the caller knows for certain that they don’t need to bounds-check and the index will be in bounds, the function can just blindly trust the index the caller provided.

5 Likes
3

i’d agree, except that the caller would also have access to the buffer directly and would not need to access items via access functions. I wonder if it’s just a temporary implementation on purpose

4 Likes
4

Looks like it was done for performance improvement

Assert below is kind of guard

assert(index < deque.len);

btw i also think that ?T is better…

1 Like
5

If you look at the docs for that function you’ll see it says

Asserts that the index is in-bounds.

By which it means, it assumes the index is in bounds.

This is quite common for a lot of the standard library. Asserts enforcing the working assumptions of code, giving you safety checks in safe builds and removing them for fast builds. It’s up to the caller to ensure that what is asserted is true. pushBack() and pushBackAssumeCapacity() is a good example on std.deque. The first “ensures” there’s at least one unused space, and the calls pushBackAssumeCapacity() which asserts that there is capacity before doing the push.

Generally, it means you can make the check once and then do multiple things to the data-structure without repeating the check every call.

9 Likes
6

There’s no performance difference between

const Deque1 = struct {
    ...
    pub fn at(deque: *const Self, index: usize) u32 {
        assert(index < deque.len);
        return deque.buffer[deque.bufferIndex(index)];
    }
};

var d1 = Deque1{}; 
...
const v1: u32 = d1.at(7);

and

const Deque2 = struct {
    ...
    pub fn at(deque: *const Self, index: usize) ?u32 {
        if (index >= deque.len) return null;
        return deque.buffer[deque.bufferIndex(index)];
    }
};

var d2 = Deque2{}; 
...
const v2: u32 = d2.at(7) orelse unreachable;

When compiled in release mode, the optimizer will treat these both the same way.

the optional would be better because it gives you the static check instead of a runtime crash

I agree, the second/optional version is more flexible (you can orelse unreachable or .? if you want the original behavior) and harder to mis-use.
(edit: I’ve changed my mind after further discussion here, I like it better how it is now)

std.ArrayList used to have this, before 0.14.0:

/// Remove and return the last element from the list.
/// Asserts the list has at least one item.
/// Invalidates pointers to the removed element.
pub fn pop(self: *Self) T {
    const val = self.items[self.items.len - 1];
    self.items.len -= 1;
    return val;
}

/// Remove and return the last element from the list, or
/// return `null` if list is empty.
/// Invalidates pointers to the removed element, if any.
pub fn popOrNull(self: *Self) ?T {
    if (self.items.len == 0) return null;
    return self.pop();
}

They were merged into a single fn pop(self: *Self) ?T, see discussion + links here: std.{ArrayList,ArrayHashMap,MultiArrayList,BoundedArray}: popOrNull() -> pop() by nektro · Pull Request #19424 · ziglang/zig · GitHub, particularly this comment.

I don’t know why Deque.at didn’t get the same treatment, maybe it was overlooked? @nektro do you have thoughts on this?

1 Like
7

for pop it makes sense to return an optional because it is meant to be used when you don’t know whether the list is empty. Deque also has popFront/popBack as well as front/back functions which all return optionals.

For at this does not really make sense, because to have a meaningful index, you usually already know the size of the list.

7 Likes
8

Ah, good point. I suppose mydeque.at(7) is acting similar to the interface for normal arrays: myarray[7]

9

The word “asserts” here is following doc comment guidance.

10

would you guys agree that it would better to shift the validity access check to the language API via ?T, rather than using the assertion.

I understand that they have the same performance, but i think the optional is more beneficial because it provides with static the static check.

1 Like
11

No, for the same reason that array index syntax ([i]) does not return an optional. The word “at” when used in an arraylike data structure here means that it is performing an operation equivalent to array indexing.

3 Likes
12

I think i understand the point you are making.

I still think that it would be beneficial to have a function that does return an optional like @pancelor suggests, am not sure what a good name for this function would be. maybe “get”?

3 Likes
13

I think the wording is fine as a standardised comment. I just don’t think it reads very naturally. That’s why I rephrased it.

In conversational language, if somebody “assets” something, they are making a statement that they believe to be true. I assert “the sun is hot”. It’s something I know is true.

These functions don’t know the index is in range. That’s why they safety-check it. Maybe I should have said they “trust but verify” the index is in range.

1 Like