pythonesque

Five basic methods of optimization

These are just some thoughts I had today about optimization and I decided to write them down before I forgot what I was thinking or changed my mind.

Suppose you have a bottleneck function, f, as part of a larger system.

1. Do exactly f, but faster.

This is the most straightforward approach. Basically, compute the exact same thing f is, but do it faster. This can include speeding up subproblems, improving the algorithm used in f itself, switching to faster hardware, performing precomputation in places that aren't time-critical (so there isn't a tradeoff from this perspective), and so on.

pythonesque

use std::fmt;

trait Trait { }

impl <T: Trait> fmt::String for T {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        Err(fmt::WriteError)
    }
}

pythonesque

// Implements http://rosettacode.org/wiki/Checkpoint_synchronization
//
// We implement this task using Rust's Barriers.  Barriers are simply thread
// synchronization points--if a task waits at a barrier, it will not continue
// until the number of tasks for which the variable was initialized are also
// waiting at the barrier, at which point all of them will stop waiting.  This
// can be used to allow threads to do asynchronous work and guarantee properties
// at checkpoints.

use std::sync::atomic::AtomicBool;

pythonesque

#![feature(overloaded_calls)]

pub struct G<T, U> {
    n: T,
}

impl<T: Add<U, T> + Clone, U> FnMut<(U,), T> for G<T, U> {
    extern "rust-call" fn call_mut(&mut self, (i,):(U,)) -> T {
        self.n = self.n + i;
        self.n.clone()

pythonesque

pub mod bitmap {
    pub type ColorComponent = u8;

    #[deriving(Clone, Default, Eq, PartialEq)]
    pub struct Pixel {
        pub r: ColorComponent,
        pub g: ColorComponent,
        pub b: ColorComponent,
    }

pythonesque

#![feature(if_let)]

extern crate arena;
extern crate rustc;

use arena::Arena;
use rustc::util::nodemap::FnvHashMap;
use std::any::{Any, AnyRefExt};
use std::cell::RefCell;
use std::collections::hashmap;

pythonesque

#![feature(unsafe_destructor)]

/*
For safety, here are some guarantees we need fulfilled for allocated types for
an allocator of size class <M, N, O>.

* <T>::Size < M

e.g. consider 1-sized struct aligned at 4096.

pythonesque

#![feature(macro_rules)]
extern crate collections;
extern crate sync;

use std::sync::{Arc, Mutex, RWLock, RWLockReadGuard};
use std::sync::atomic::{AtomicBool, AtomicPtr, AtomicUint, Ordering, Relaxed, SeqCst};
use std::ptr;
use std::ptr::{RawMutPtr};
use std::slice::Items;

pythonesque

• Start Date: 2014-11-10
• RFC PR: (leave this empty)
• Rust Issue: (leave this empty)

Summary

I propose altering the Send trait as proposed by RFC #17 as follows:

• Remove the implicit 'static bound from Send.

pythonesque

use std::collections::{dlist, DList, HashSet, Deque};
use std::hash::Hash;
use std::iter;
use std::default::Default;

pub struct LinkedHashSet<'a, T: 'a> where T: Hash + Eq {
    // Important: HashSet must come after DList, since destructors run in
    // reverse order.  Otherwise we'd have use after free (potentially).
    element_list: DList<T>,
    element_set: HashSet<&'a T>,