8
\$\begingroup\$

Given an integer n as input, write a function that dynamically allocates n bytes and returns their address.

Rules

  • The allocator must be able to dynamically allocate memory at runtime.
  • It doesn't matter where the memory is allocated to or in what form, as long as it's allocated in a valid location which can be read from and written to.
  • Allocated memory locations must be unique and not override or cross already-allocated locations.
  • You don't have to write the code in a way such that the memory can be deallocated later.
  • It might be obvious, but you are not allowed to use a programming language's or standard library's built in allocator. For example, making a function return the result of malloc or new is not a valid solution.
  • You don't need to worry about out-of-memory errors. Assume big amounts of memory are never allocated.
  • Efficiency and speed are not a factor. The only requirement for the challenge is the shortest code, in bytes.
  • Standard loopholes are not allowed.
\$\endgroup\$
7
  • 3
    \$\begingroup\$ Welcome to Code Golf and nice first question! For future reference, we recommend using the Sandbox to get feedback on challenge ideas before posting them to main \$\endgroup\$ Nov 7, 2021 at 12:49
  • 2
    \$\begingroup\$ Maybe include a not at the top that this is challenge is only for languages where the programmer can allocate memory manually. (This excludes a great many of the most popular languages here.) \$\endgroup\$
    – Adám
    Nov 7, 2021 at 12:50
  • 8
    \$\begingroup\$ Where is the line regarding what's "a programming language's or standard library's built in allocator"? It feels a little undefined  malloc is not allowed, but what about other POSIX functions like mmap? Linux system functions like sbrk? \$\endgroup\$ Nov 7, 2021 at 23:50
  • 1
    \$\begingroup\$ @TheShwarma To me (and most people, probably) it isn't, as built-in bans are often avoided and challenges are typically written to be possible for as many languages as possible to compete in. There's absolutely nothing wrong with not doing either of those, but as Adám said it's always a good idea to make that clear. \$\endgroup\$ Nov 8, 2021 at 4:12
  • 1
    \$\begingroup\$ I'm going to close this as unclear since it is not apparent what counts as "a programming language's or standard library's built in allocator". It most the existing answers are already pretty close to an edge case on this rule, so it is imperative that this is clarified before more answers of questionable validity arrive. \$\endgroup\$
    – Wheat Wizard
    Nov 8, 2021 at 10:36

6 Answers 6

6
\$\begingroup\$

C (gcc), 51 bytes

#include<sys/mman.h>
#define m(n)mmap(0,n,7,33,0,0)

Try it online!

-4 bytes thanks to ceilingcat by switching to a function-like macro.


mmap is a system call which maps a file into virtual address space. On Linux, it can also be used in MAP_ANONYMOUS mode, where it doesn't map any file at all, but just "creates" memory out of thin air. The POSIX-portable method would be to open and map the device file /dev/zero, which is full of infinite null bytes.

The first argument is a "hint" to the kernel on where to allocate it close to, which can help improve caching. We can just leave it as NULL (or 0, which is golfier) for a basic allocator, though.

The second argument is the size, n.

The third argument is the the memory protection flags of the chunk. 7 is PROT_READ | PROT_WRITE | PROT_EXEC to allow all operations.

The fourth argument, flags, sets allocation options. 33 is MAP_ANONYMOUS | MAP_PRIVATE, which allocates process-private memory without a backing file descriptor. This is practically equivalent to the portable POSIX method which involves opening and mapping /dev/zero, but it's much shorter.

The final parameters are the file descriptor (whose value is ignored, because we're using MAP_ANONYMOUS), and offset, which should be 0 because there's no file.

You can read more about mmap in its manual page.


C (gcc) (invalid, but still interesting!), 35 bytes

m(int(*f)(),int n){char p[n];f(p);}

Try it online!

Using variable-length arrays, it's possible to get dynamic memory allocation on the stack. The memory lives only as long as its scope is running, so it has to be returned using a callback function and only used within that callback (which is not an allowed I/O method, so this answer is invalid). I'm not sure if this would be valid even then, because it might count as using a built in allocator.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ You could start a meta discussion on whether it's acceptable to take a callback - After all, returning a Promise in JS is acceptable, and that requires .then(callback) to use the result. \$\endgroup\$
    – emanresu A
    Nov 7, 2021 at 18:56
2
\$\begingroup\$

C (gcc), 49 \$\cdots\$ 36 34 bytes

b[1<<24];m;r;f(n){r=b+m;m+=n;r=r;}

Try it online!

Saved 2 bytes thanks to ceilingcat!!!

Of course you don't say how much memory is needed, this will work with \$16\$+ million bytes.

Commented

b[1<<24];        // our memory buffer as an array of double words  
m;               // declare global variable m to track where free 
                 // memory is      
r;               // declare r for golfing returning without return
                 // and saving current position before updating m   
f(n){            // a function returning an int which will work
                 // as a void* pointer and taking an int 
                 // parameter n, this will return 4x the number 
                 // of bytes asked for  
    r=b+m        // store current position in buffer   
    m+=n;        // update where next request for memory will be  
    r=r;         // return a pointer for n bytes of memory (actually  
                 // n*4 bytes but that'll do for n bytes) 
}
\$\endgroup\$
10
  • \$\begingroup\$ Isn't the return value of a function without a return statement undefined? Does this only work if the compiler happens to choose the right register for use, or is it guaranteed? \$\endgroup\$
    – throx
    Nov 8, 2021 at 0:48
  • \$\begingroup\$ For example, the code posted in tio.run core dumps if you add '-O2' as a compiler flag. \$\endgroup\$
    – throx
    Nov 8, 2021 at 2:20
  • \$\begingroup\$ Also, as an improvement, make the array an int (so no type declaration, five bytes saved) and use void* as the return type. Nothing in the contest says you can't waste a ton of memory just because. \$\endgroup\$
    – throx
    Nov 8, 2021 at 6:11
  • \$\begingroup\$ @throx No, the return type is determined by the function signature which is char* f(int) (the int is by default). The r=r is a golfing hack and they don't play well with compiler optimisations. \$\endgroup\$
    – Noodle9
    Nov 8, 2021 at 9:26
  • \$\begingroup\$ @throx In general a lot of C golf hacks are exploiting undefined behaviour, but they work for the given compiler with the compiler options used. Some will also only work on certian OS's, but that will be posted with the code (eg on Linux). \$\endgroup\$
    – Noodle9
    Nov 8, 2021 at 11:07
1
\$\begingroup\$

C (gcc) on Linux, 45 bytes

#include<unistd.h>
int*a(n){return sbrk(n);}

Try it online!

The sbrk system call on Linux moves the program break by the specified number of bytes, and returns a pointer to the old program break. This has the effect of allocating that many bytes of uninitialized memory and returning a pointer.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ Suggestion - use <zconf.h> instead of <unistd.h> for a 1 character saving. <rrd.h> is better, but isn't on tio.run. If Noodle9's elimination of 'return' is legitimate, then do that as well (but it will core dump on a -O2 build). \$\endgroup\$
    – throx
    Nov 8, 2021 at 2:26
  • 1
    \$\begingroup\$ This is equivalent to the submission sbrk, which is surely in effect a built-in allocator? \$\endgroup\$
    – pxeger
    Nov 8, 2021 at 6:38
1
\$\begingroup\$

ZX Spectrum (48K model) BASIC, 19 bytes

LET r=VAL "65367"-n: CLEAR r-SGN PI

65367 is the default RAMTOP for the 48K model (assuming the RAM is not faulty). CLEAR sets the new RAMTOP lower by the requested amount, minus one, so that you can use the reserved RAM starting from the value returned in r by whatever combination of PEEK and POKE you desire. Note that while the BASIC has subroutines, they cannot return values, so the return value is assigned to the variable r.

Using VAL "65367" instead of plain number golfed 2 bytes (the number would be stored in additional 5 bytes otherwise); SGN PI instead of 1 similarly golfed 4 bytes; keywords take 1 byte each.

The standard allocator (that we cannot use) is of course DIM.

\$\endgroup\$
0
0
\$\begingroup\$

Python, 28 bytes

def m(n):return bytearray(n)
\$\endgroup\$
1
0
\$\begingroup\$

C (gcc), 44 bytes

char a[~0U],*p=a;char*m(n){return p+=n,p-n;}

\$\endgroup\$

Not the answer you're looking for? Browse other questions tagged or ask your own question.