1. 18 Mar, 2019 2 commits
    • Yorick Peterse's avatar
      Rewrite the process scheduler from the ground up · 3e5882be
      Yorick Peterse authored
      The old scheduler was a little over two years old, and due for a
      rewrite. While it worked, it was not very efficient and many features
      were bolted on top; process pinning being an example.
      The new scheduler relies less heavy on locking, only using mutexes
      paired with condition variables to wake up sleeping threads. This will
      allow it to scale much better as the number of threads goes up.
      Another big benefit is clearer code. The old scheduler's code was a
      mess, largely because we focused more on getting a proof of concept out
      instead of building a scheduler for the next few years.
      == Suspending and rescheduling processes
      As part of this rewrite, the way timeouts and rescheduling of processes
      is handled is also rewritten. When a process is suspended and receives a
      message, the sender will try to reschedule it immediately. This makes
      sending messages a little bit more expensive, but allows for much faster
      rescheduling of processes. This also removes the need for a separate
      thread to perform a linear scan over a list of processes to determine
      which ones need to be rescheduled.
      Processes that suspend themselves with a timeout are stored in a binary
      heap, managed by a separate thread. Communication with this thread is
      done using a channel, offloading most of the work to the separate
      timeout thread. When a process with a timeout is rescheduled, its entry
      in the heap is marked as invalid instead of being removed. This makes
      the operation a constant time operation, at the cost of the binary heap
      getting fragmented. To combat fragmentation, the timeout thread will
      periodically remove invalid entries from the heap.
      Rescheduling processes is done entirely using atomic operations, instead
      of using mutexes. This requires some careful coding to take into account
      multiple threads trying to reschedule the same process, but should allow
      all of this to scale much better.
      The new approach of suspending and rescheduling processes requires one
      additional word of memory per process. This memory is used to mark the
      process as suspended, and to optionally store a pointer to its timeout
      (if one was used).
      == Message counts
      The number of messages in a mailbox is now stored explicitly using an
      atomic integer, instead of obtaining this from the synchronised
      data structures internal to a mailbox. This requires one word of extra
      memory per process, but makes it much cheaper to check if a process has
      messages. This is important, because when rescheduling a process such
      checks are performed several times.
      == Asynchronous IO and further improvements
      While this commit does not add support for asynchronous IO operations,
      the rewrite will make it easier to do so in future commits. The process
      lookup table also remains unchanged, but we're currently investigating
      if we can get rid of PIDs and the lookup table entirely; potentially
      speeding up process spawning by quite a bit.
    • Yorick Peterse's avatar
      Use Rust stable for rustfmt · cdaaa5f7
      Yorick Peterse authored
  2. 19 Feb, 2019 1 commit
  3. 28 Dec, 2018 1 commit
    • Yorick Peterse's avatar
      Use BufReader when reading bytecode from files · d80c4c30
      Yorick Peterse authored
      Using a 32KB buffer this allows us to drastically reduce the time spent
      parsing bytecode files. Consider the following program:
          import std::ansi
          import std::ffi
          import std::fs
          import std::mirror
          import std::stdio::stderr
          import std::stdio::stdin
          import std::stdio::stdout
          import std::time
          stdout.print('hello world')
      Prior to these changes, running this program (ignoring the compilation
      itme) takes around 240 milliseconds. With these changes, this is reduced
      to 20 milliseconds: a 12x improvement.
  4. 26 Dec, 2018 8 commits
  5. 25 Dec, 2018 1 commit
    • Yorick Peterse's avatar
      Reorganise and test std::time · 7f0cb46b
      Yorick Peterse authored
      std::time is now broken up into two modules:
      1. std::time, which provides time related types.
      2. std::time::duration, which provides the Duration type.
      This separation allows for the use of module methods to construct a
      Duration using different time units, instead of using methods defined on
      Duration itself. This means that instead of this:
          import std::time::Duration
      You now write this:
          import std::time::duration
      == Renaming MonotonicTime to Instant
      MonotonicTime has been renamed to "Instant", which is a bit shorter and
      much easier to type. A new method has been added as well: "elapsed".
      This method can be used to measure the time that has elapsed since the
      Instant was created.
      == Adding and subtracting SystemTime and Instant
      The methods + and - for SystemTime and Instant no longer accept a
      ToFloat, instead they require a Duration. Accepting a ToFloat would
      allow you to add a SystemTime to another SystemTime, or add an Instant
      to an Instant. Neither make sense, so instead we now require the use of
      a Duration. This means that instead of this:
          import std::time
          time.now + 5
      You now have to write this:
          import std::time
          import std::time::duration
          time.now + duration.from_seconds(5)
      == Tests
      Finally, both std::time and std::time::duration have tests. These tests
      uncovered a few bugs in the implementation of SystemTime, which have
      been resolved.
  6. 23 Dec, 2018 1 commit
  7. 22 Dec, 2018 1 commit
    • Yorick Peterse's avatar
      Added method Float.to_bits · a4c2d681
      Yorick Peterse authored
      This method can be used to obtain the bitwise representation of a Float.
      This in turn can be used to perform an approximate equality comparison
      by checking bits of a Float.
  8. 19 Dec, 2018 4 commits
    • Yorick Peterse's avatar
      Rename Immix bitmap structures to bytemaps · 57247e71
      Yorick Peterse authored
      These structures have been bytemaps for quite a while now, so let's
      start calling them that.
    • Yorick Peterse's avatar
      Fix lookups in ObjectMirror.implements_trait? · 9af64983
      Yorick Peterse authored
      This method would mistakingly keep looking up traits in the mirror
      subject, instead of using the objects in the prototype chain.
    • Yorick Peterse's avatar
      Added tests for std::trait · e33ed34f
      Yorick Peterse authored
    • Yorick Peterse's avatar
      Move all "class" methods to module methods · 1a577430
      Yorick Peterse authored
      In the past I have gone back and forth a bit on the idea of using
      class/static methods or not. With this commit I'm making a final
      decision on this topic: Inko will not have class/static methods, at
      least not until 1.0. Instead, Inko will use module methods. This means
      that the following methods have been changed:
      * HashMap.from_array  -> std::hash_map.from_array
      * Trait.implement_for -> std::trait.implement
      * Integer.from_string -> std::integer.parse
      * Float.from_string   -> std::float.parse
      To make this happen some compiler changes had to be made to optimise
      `hash_map.from_array` and to use `trait.implement` instead of
  9. 17 Dec, 2018 1 commit
    • Yorick Peterse's avatar
      Enforce a limit on bytecode input sizes · 26f0023c
      Yorick Peterse authored
      This adds limits to various parts of the bytecode parser that are
      enforced when reading various literals, such as strings and Compiled
      Code objects. These limits prevent the VM from crashing with an OOM
      error when reading malformed (or _very_ large) bytecode files.
  10. 16 Dec, 2018 1 commit
    • Yorick Peterse's avatar
      Parsing of Strings into Floats and Integers · 6558d6b5
      Yorick Peterse authored
      This adds support for parsing a String into a Float and an Integer.
      There are two ways of doing so:
      1. By sending `to_integer` or `to_float` to a `String`.
      2. Using `Integer.from_string` or `Float.from_string`.
      Using `to_integer` and `to_float` will perform a lossy conversion:
      returning 0 or 0.0 for invalid input. Using the `from_string` methods
      will result in a strict conversion, with an error being thrown for
      invalid input.
      Fixes #134
      Fixes #156
  11. 11 Dec, 2018 3 commits
    • Yorick Peterse's avatar
      Remove SystemTime.format and SystemTime.parse · a38d0f56
      Yorick Peterse authored
      At least for the time being Inko will not provide parsing and formatting
      of times in the standard library. There are many different input and
      output formats people may need to work with, and Inko can't possibly
      support all of them. I am also not sure what format Inko _would_ support
      at this time. Since supporting this is not crucial at this time, we'll
      simply skip it altogether.
      See #96 for more information.
    • Yorick Peterse's avatar
      Fixed racy tests for std::env · 4a985130
      Yorick Peterse authored
      These tests could randomly fail due to some removing an environment
      variable and expecting it to remain removed, while other tests would
      re-add the variable.
      Fixes #154
    • Yorick Peterse's avatar
      Move std::reflection into std::mirror · b3c7e36f
      Yorick Peterse authored
      This moves all code from `std::reflection` into `std::mirror`, finally
      removing the need for the two separate modules. We also renamed
      `kind_of?` to `implements_trait?`, and implemented both it and
      `instance_of?` in pure Inko. This in turn allows us to remove some
      specialised VM instructions.
      Fixes #153
  12. 10 Dec, 2018 1 commit
    • Yorick Peterse's avatar
      Tests for std::process and remove receive_if · bf0d6d66
      Yorick Peterse authored
      This adds tests for `std::process`, and removes
      `std::process.receive_if`. The `receive_if` method has always been a bit
      of a weird method. It was originally meant to allow some form of pattern
      matching on messages, but this turned out to be less useful than hoped
      due to the return type still being `Dynamic`.
      The `timeout` argument was also not used properly, and solving this
      would not be easily doable.  This is because there was no single
      operation to apply the timeout to, instead the implementation of
      `receive_if` contained two `receive` calls, and some other logic.
      Handling all this would require us to keep track of the elapsed time
      ourselves, which is rather tricky should the process be stuck in a
      blocking receive.
      Instead of trying to come up with all kinds of crazy ideas, I have opted
      to simply remove `receive_if` for the time being. This makes some test
      runner code a bit more fragile (in theory), but I doubt this will pose
      any real problems any time soon.
  13. 09 Dec, 2018 4 commits
  14. 08 Dec, 2018 3 commits
    • Yorick Peterse's avatar
      Reset maiting state when there is a process · a51d1b62
      Yorick Peterse authored
      When a process was waiting for a message and there is one now, we need
      to make sure we reset the waiting state.
    • Yorick Peterse's avatar
      Removed storing of entire process statuses · 86cadf10
      Yorick Peterse authored
      Obtaining the process status has always been a bit questionable. For
      one, it's not particularly useful to see that a process is running or
      being garbage collected. Second, it requires a full 8 bytes of memory
      per process to store.
      In this commit, we drop the storing of full process statuses, and add a
      boolean flag "waiting for message" that we use instead where necessary.
      Currently this won't reduce the size of a process due to alignment
      requirements, but in the future we may be able to work around this by
      reducing the size of other fields.
    • Yorick Peterse's avatar
      Use two survivor spaces for local allocators · 3caf9631
      Yorick Peterse authored
      Using three survivor spaces instead of two does not really offer many
      benefits, as objects surviving two collections are likely to also
      survive a third. Removing one survivor space reduces the size of a
      process by at least 32 bytes.
  15. 07 Dec, 2018 4 commits
  16. 06 Dec, 2018 4 commits
    • Yorick Peterse's avatar
      Clean up code for Clippy on Rust 1.31 · 05d8972f
      Yorick Peterse authored
      The latest version of Clippy introduced some new lints, and will now
      complain about the deprecated syntax. Unfortunately, the new tool_lints
      syntax doesn't work on older Rust versions so we can not yet start
      using it.
      This commit also refactors various disabled Clippy lints away. Some of
      the disable lines are still necessary as Clippy is overly pedantic, but
      this at least gets rid of a large portion of them.
    • Yorick Peterse's avatar
      Move histograms from buckets to allocators · f0b6fde0
      Yorick Peterse authored
      This moves the mark and available histograms outside of the Bucket type
      and into the local and mailbox allocators, reducing the memory required
      per process by at least 100 bytes. Behaviour wise nothing changes, as
      for the LocalAllocator we would evacuate objects for all Buckets the
      moment we'd find one that was fragmented.
    • Yorick Peterse's avatar
      Use i8 for the bucket ages · 5aaa746b
      Yorick Peterse authored
      An i8 is large enough to store all values, but requires only half the
      space compared to an i16. This reduces the size of the Process type by
      24 bytes.
    • Yorick Peterse's avatar
      Use u32 for block allocation thresholds · ff158aae
      Yorick Peterse authored
      An u32 is enough to represent 128 TB worth of Immix blocks, and means a
      GenerationConfig only takes up 8 bytes of space, instead of 16 bytes.