15
\$\begingroup\$

Overview

Sometimes in the real world, you're in a situation where you need to run a program on a very specialized computer, and you don't care how long it takes to run, but the computer has very limited memory. So, rather than optimizing for speed, you have to optimize for low memory footprint.

The point of this challenge genre would be to pose challenges where getting a small program or a fast program may not be challenging, but trying to use as little memory as possible to solve the problem is an interesting goal.

Winning

Here are some examples of objective winning criteria for this genre:

  • lowest peak memory usage
  • lowest average memory usage
  • lowest peak stack size (for stack-based languages; could be expanded to other languages by enforcing use of a stack for all memory allocation/deallocation; tape-based languages like brainfuck would have lowest maximal tape position)

More than likely, like , the memory usage will be measured on the challenge author's computer. Luckily, there are some helpful tools and loads of useful SO/SE questions (1, 2, 3) to help the challenge author in measuring memory usage.

Additionally, some custom memory management tools/libraries could be written to get realtime information about memory allocation and deallocation (like by writing a custom malloc function in C).

Tag name

I propose the tag name for this genre be .

Request for comments

  • What other details/requirements would need to be added?
  • What other winning criteria could be used?
  • What issues are present in this proposal that my sleepy brain isn't catching?
\$\endgroup\$
  • 20
    \$\begingroup\$ Some language's interpreters have a massive amount of memory overhead which might make it really hard to get accurate results. Maybe something like the GOLF CPU would help to determine objective scores? \$\endgroup\$ – Martin Ender Feb 21 '16 at 11:17
  • 5
    \$\begingroup\$ There's also the possibility of scoring by space complexity, but that should definitely be distinguished from counting raw bytes, much like we have fastest-code and fastest-algorithm. I'm also not a huge fan of calling what you're proposing memory-golf, but unfortunately I don't have the better suggestion either right now. \$\endgroup\$ – Martin Ender Feb 21 '16 at 16:19
  • 1
    \$\begingroup\$ @MartinBüttner Another winning criteria I was considering would involve only counting the memory used by the program, so the startup memory usage by the interpreter wouldn't be counted. I couldn't think of how to put that into words last night. \$\endgroup\$ – Mego Feb 21 '16 at 16:39
  • \$\begingroup\$ I suppose you could compare the memory usage for the smallest sensible problem instance with the memory usage for a large problem instance. Although this might be gameable I suppose... \$\endgroup\$ – Martin Ender Feb 21 '16 at 16:40
  • 3
    \$\begingroup\$ @MartinBüttner Another thing to consider is that the advantages that languages like C and ASM have (by virtue of being "closer to the metal") in this type of challenge is virtually no different than the advantages that golfing languages have in code golf. The important thing to remember is that a challenge is also a competition within languages, not just a competition between languages. \$\endgroup\$ – Mego Feb 21 '16 at 17:54
  • 2
    \$\begingroup\$ Of course it is. I didn't mean to imply that the overhead of a language's interpreter is unfair. But that it might be a lot larger than the memory used for the actual problem in some cases, and that it could vary based on the system state, which would make comparisons within the language itself harder. \$\endgroup\$ – Martin Ender Feb 21 '16 at 18:30
  • 2
    \$\begingroup\$ I'd argue for smallest-space to be the tag name (and its counterpart space-complexity) \$\endgroup\$ – Nathan Merrill Feb 22 '16 at 16:56
  • 2
    \$\begingroup\$ With apologies to Bill Gates, we could call it 640k-golf \$\endgroup\$ – AdmBorkBork Feb 23 '16 at 15:09
  • 1
    \$\begingroup\$ For what it's worth, I think this is an AWESOME new tag and can't wait to use it ;) \$\endgroup\$ – J Atkin Feb 25 '16 at 2:35
  • \$\begingroup\$ @JAtkin I plan on sandboxing a challenge for the tag soon, once I work out all the details of measuring memory usage fairly. \$\endgroup\$ – Mego Feb 25 '16 at 2:42
  • \$\begingroup\$ I don't think the memory is practically usually measured in space complexity, but in the form f(n)+o(f(n)) (or f(n)+O(g(n))), where f(n) is a function that usually appeared in a complexity, with a constant factor. \$\endgroup\$ – jimmy23013 Feb 25 '16 at 9:05
  • \$\begingroup\$ Maybe use a VM to calculate? \$\endgroup\$ – Hipe99 Mar 2 '16 at 21:36
  • 1
    \$\begingroup\$ I like this idea, but a Python runtime doing literally nothing allocates 21 megabytes, and Ruby uses 12 megs. For instance, Pyth is written in Python and needs Python's runtime, and GS uses Ruby. "Don't use those languages!", you say, but not a lot of languages are implemented in (memory-efficient) C, and the ones that are happen to be less popular. This seems like a great challenge, but there aren't that many Assembler programmers here (are there?). \$\endgroup\$ – cat Mar 3 '16 at 18:45
  • \$\begingroup\$ On the other hand, gforth only uses 2 mb, and I bet I could craft a super minimal implementation for bytecode \$\endgroup\$ – cat Mar 3 '16 at 18:48
  • \$\begingroup\$ What about considering only memmory alocated by the program itself (i.e. sum of memory cost of declared variables/objects and/or data stack)? \$\endgroup\$ – dnep Mar 4 '16 at 21:07

You must log in to answer this question.

Browse other questions tagged .