<commit_before>import events
import heapq
import draw
import config
import pdb
import logging
import sched_adaptive
import copy # for heapq


# We assume that the propagation time is zero. The cost for
# transporting messages is captured in t_send and t_receive.
T_PROPAGATE = 0

assert T_PROPAGATE == 0 # Otherwise sched_adaptive's
                        # optimize_scheduling needs an update

class bcolors:
    HEADER = '\033[95m'
    OKBLUE = '\033[94m'
    OKGREEN = '\033[92m'
    WARNING = '\033[93m'
    FAIL = '\033[91m'
    ENDC = '\033[0m'
    BOLD = '\033[1m'
    UNDERLINE = '\033[4m'

class Protocol(object):
    """Represent a protocol that is executed  by the Simulator
    """

    def set_initial_state(self, eval_context, root):
        """Initialize protocol execution

        @param eval_context A reference to the evaluate instance
        executing the Simulation.

        @param root The root node of the topology
        """

    def idle_handler(self, eval_context, core, time):
        """Executed  when a core because idle

        @param eval_context A reference to the evaluate instance
        executing the Simulation.

        @param core The core that has become idel

        @param time The current time
        """

    def get_name(self):
        """Representative name for the protocol

        """

    def receive_handler(self, eval_context, core, from_core, time):
        """Triggered when a message was received on <core>

        """
        return True

    def is_terminated(self, eval_context):
        """Indicate if the protocol is terminated

        Normally, this can be determined by the execution process
        directly. Otherwise, it can be configured here

        """
        return True


class AB(Protocol):
    """Atomic broadcast protocol
    """
    def __init__(self):
        # Keep track of which nodes are active
        # Lists of nodes that:
        #  -> received the message already (cores_active)
        self.cores_active = []

        # dictionary of core -> time tuples indicating the order in which
        # cores become active (e.g. receive the message first)
        #
        # This is AFTER receiving the initial message
        self.log_first_message = {}

        # dictionary of core -> time tuples indicating the order in which
        # cores become idle (e.g. are done sending)
        self.log_idle = {}

    def get_name(self):
        return 'atomic broadcast'

    def set_initial_state(self, eval_context, root):
        """Evaluate cost starting at root of overlay
        """
        eval_context.schedule_node(root)
        self.cores_active = [root]


    def idle_handler(self, eval_context, core, time):
        """Idle nodes in the atomic broadcast will send messages to nodes that
        have not yet seen the message.

        The scheduler decides where messages should be sent.

        """

        # Get a list of neighbors from the scheduler
        nb = eval_context.schedule.find_schedule(core, self.cores_active)
        assert isinstance(nb, list)
        assert isinstance(self.cores_active, list)

        # Ignore all nodes that received the message already
        nb_filtered = [ tmp for (_, tmp) in nb if tmp not in self.cores_active ]

        if len(nb_filtered) > 0:
            dest = nb_filtered[0]
            cost = eval_context.get_send_cost(core, dest)

            # Adaptive models: need to add edge
            if not eval_context.topology.has_edge((core,dest)):
                eval_context.topology.add_edge(
                    (core, dest),
                    eval_context.model.graph.edge_weight((core, dest)))

            eval_context.visu.send(core, dest, time, cost)
            print 'Send(%d,%s,%s) - cost %d' % \
                (eval_context.sim_round, str(core), str(dest), cost)

            send_compl = time + cost

            # Make receiver active
            eval_context.schedule_node(dest, send_compl, core)
            self.cores_active.append(dest)

            # Add send event to signal that further messages can be
            # sent once the current message completed the current send
            # operation.
            heapq.heappush(\
                eval_context.event_queue, \
                    (send_compl, events.Send(core, None)))

        else:
            assert not core in self.log_idle
            self.log_idle[core] = time


    def receive_handler(self, eval_context, core, from_core, time):
        """Triggered when a message was received on <core>

        """
        time += eval_context.model.get_receive_cost(from_core, core)

        assert not core in self.log_first_message
        self.log_first_message[core] = time
        return True


    def is_terminated(self, eval_context):
        """Protocol is terminated, output core timing

        """

        if not eval_context.topo.options.get('shuffle', False):
            return True

        # We reshuffle until as long as we still optimize the tree
        optimize = True

        while optimize:

            # These are the ones that we want to optimize, that's the time
            # at which cores first receive a message
            _first = sorted(self.log_first_message.items(), key=lambda x: x[1], reverse=True)
            for (core, time) in _first:
                print 'first seen: %2d %8.2f' % (core, time)


            # That's the time at which a core is done sending a
            # messages. Cores that finish early have some slack to send to others
            _log_idle = sorted(self.log_idle.items(), key=lambda x: x[1])
            for (core, time) in _log_idle:
                print 'idle: %2d %8.2f' % (core, time)

            ((first, f_time), (last, l_time)) = (_first[0], _log_idle[0])

            # Check if (first->last) would optimize the tree
            slack = (f_time-l_time)

            t_send = eval_context.model.get_send_cost(first, last)
            t_receive = eval_context.model.get_receive_cost(first, last)

            cost_direct =  t_send + t_receive

            # Replace if:
            # 1) we have enough slack for an additonal message and
            # 2) the additional message is not already part of the schedule
            #
            if cost_direct <= slack and \
               not eval_context.topology.has_edge((last, first)): 

                optimize = True
                print 'schedule: replacing', last, first

                # Replace in schedule
                eval_context.schedule.replace(last, first)

                # Remove exising edges from topology
                num = 0
                for c in eval_context.model.get_cores():
                    if eval_context.topology.has_edge((c, first)):
                        eval_context.topology.del_edge((c, first))
                        num += 1
                assert num == 1
                # Add new one
                eval_context.topology.add_edge((last, first),
                                               eval_context.model.graph.edge_weight((last, first)))

                # the first core now is busy for longer
                self.log_idle[last] = l_time + t_send

                # the receiving core is done earlier
                _first_new = l_time + t_send + t_receive + T_PROPAGATE

                # Floating point comparison - make sure the two ways
                # of calculating are (approximately) the same
                c1 = self.log_first_message[first] - (slack-cost_direct)
                c2 = _first_new
                assert abs(c1-c2) < 1.0

                self.log_first_message[first] = _first_new

                print 'slack: %2d %2d %10.2f %10.2f %5s' % \
                    (first, last, slack, cost_direct, 'yes' if optimize else 'no')


                if eval_context.topo.options.get('sort', False):
                
                    # Optimize the send order within each node!
                    _log_idle, _log_fist_message = eval_context.schedule.optimize_scheduling()

                    # I'm already scared of this!
                    self.log_idle = _log_idle
                    self.log_first_message = _log_fist_message

            else:<commit_msg>Optimization: sort FIRST before shuffling, only sort if the result is faster<commit_after>import events
import heapq
import draw
import config
import pdb
import logging
import sched_adaptive
import copy # for heapq


# We assume that the propagation time is zero. The cost for
# transporting messages is captured in t_send and t_receive.
T_PROPAGATE = 0

assert T_PROPAGATE == 0 # Otherwise sched_adaptive's
                        # optimize_scheduling needs an update

class bcolors:
    HEADER = '\033[95m'
    OKBLUE = '\033[94m'
    OKGREEN = '\033[92m'
    WARNING = '\033[93m'
    FAIL = '\033[91m'
    ENDC = '\033[0m'
    BOLD = '\033[1m'
    UNDERLINE = '\033[4m'

class Protocol(object):
    """Represent a protocol that is executed  by the Simulator
    """

    def set_initial_state(self, eval_context, root):
        """Initialize protocol execution

        @param eval_context A reference to the evaluate instance
        executing the Simulation.

        @param root The root node of the topology
        """

    def idle_handler(self, eval_context, core, time):
        """Executed  when a core because idle

        @param eval_context A reference to the evaluate instance
        executing the Simulation.

        @param core The core that has become idel

        @param time The current time
        """

    def get_name(self):
        """Representative name for the protocol

        """

    def receive_handler(self, eval_context, core, from_core, time):
        """Triggered when a message was received on <core>

        """
        return True

    def is_terminated(self, eval_context):
        """Indicate if the protocol is terminated

        Normally, this can be determined by the execution process
        directly. Otherwise, it can be configured here

        """
        return True


class AB(Protocol):
    """Atomic broadcast protocol
    """
    def __init__(self):
        # Keep track of which nodes are active
        # Lists of nodes that:
        #  -> received the message already (cores_active)
        self.cores_active = []

        # dictionary of core -> time tuples indicating the order in which
        # cores become active (e.g. receive the message first)
        #
        # This is AFTER receiving the initial message
        self.log_first_message = {}

        # dictionary of core -> time tuples indicating the order in which
        # cores become idle (e.g. are done sending)
        self.log_idle = {}

    def get_name(self):
        return 'atomic broadcast'

    def set_initial_state(self, eval_context, root):
        """Evaluate cost starting at root of overlay
        """
        eval_context.schedule_node(root)
        self.cores_active = [root]


    def idle_handler(self, eval_context, core, time):
        """Idle nodes in the atomic broadcast will send messages to nodes that
        have not yet seen the message.

        The scheduler decides where messages should be sent.

        """

        # Get a list of neighbors from the scheduler
        nb = eval_context.schedule.find_schedule(core, self.cores_active)
        assert isinstance(nb, list)
        assert isinstance(self.cores_active, list)

        # Ignore all nodes that received the message already
        nb_filtered = [ tmp for (_, tmp) in nb if tmp not in self.cores_active ]

        if len(nb_filtered) > 0:
            dest = nb_filtered[0]
            cost = eval_context.get_send_cost(core, dest)

            # Adaptive models: need to add edge
            if not eval_context.topology.has_edge((core,dest)):
                eval_context.topology.add_edge(
                    (core, dest),
                    eval_context.model.graph.edge_weight((core, dest)))

            eval_context.visu.send(core, dest, time, cost)
            print 'Send(%d,%s,%s) - cost %d' % \
                (eval_context.sim_round, str(core), str(dest), cost)

            send_compl = time + cost

            # Make receiver active
            eval_context.schedule_node(dest, send_compl, core)
            self.cores_active.append(dest)

            # Add send event to signal that further messages can be
            # sent once the current message completed the current send
            # operation.
            heapq.heappush(\
                eval_context.event_queue, \
                    (send_compl, events.Send(core, None)))

        else:
            assert not core in self.log_idle
            self.log_idle[core] = time


    def receive_handler(self, eval_context, core, from_core, time):
        """Triggered when a message was received on <core>

        """
        time += eval_context.model.get_receive_cost(from_core, core)

        assert not core in self.log_first_message
        self.log_first_message[core] = time
        return True


    def is_terminated(self, eval_context):
        """Protocol is terminated, output core timing

        """

        if not eval_context.topo.options.get('shuffle', False):
            return True

        # We reshuffle until as long as we still optimize the tree
        optimize = True

        while optimize:

            # --------------------------------------------------
            # Reorder tree FIRST
            # --------------------------------------------------
            
            if eval_context.topo.options.get('sort', False):

                # Optimize the send order within each node!
                _log_idle, _log_fist_message = eval_context.schedule.optimize_scheduling()

                # Make sure new Schedule is _actually_ better
                _slowest_old = sorted(self.log_first_message.items(), key=lambda x: x[1], reverse=True)
                _slowest_new = sorted(_log_fist_message.items(), key=lambda x: x[1], reverse=True)
                
                # Only reorder in case the new schedule is faster:
                # this is a bit weird, I though we would _always_ be
                # faster with this.
                if abs(_slowest_new[0][1]-_slowest_old[0][1])<1 or True:
                
                    # I'm already scared of this!
                    self.log_idle = _log_idle
                    self.log_first_message = _log_fist_message

            
            # These are the ones that we want to optimize, that's the time
            # at which cores first receive a message
            _first = sorted(self.log_first_message.items(), key=lambda x: x[1], reverse=True)
            for (core, time) in _first:
                print 'first seen: %2d %8.2f' % (core, time)


            # That's the time at which a core is done sending a
            # messages. Cores that finish early have some slack to send to others
            _log_idle = sorted(self.log_idle.items(), key=lambda x: x[1])
            for (core, time) in _log_idle:
                print 'idle: %2d %8.2f' % (core, time)

            ((first, f_time), (last, l_time)) = (_first[0], _log_idle[0])

            # Check if (first->last) would optimize the tree
            slack = (f_time-l_time)

            t_send = eval_context.model.get_send_cost(first, last)
            t_receive = eval_context.model.get_receive_cost(first, last)

            cost_direct =  t_send + t_receive

            # Replace if:
            # 1) we have enough slack for an additonal message and
            # 2) the additional message is not already part of the schedule
            #
            if cost_direct <= slack and \
               not eval_context.topology.has_edge((last, first)): 

                optimize = True
                print 'schedule: replacing', last, first

                # Replace in schedule
                eval_context.schedule.replace(last, first)

                # Remove exising edges from topology
                num = 0
                for c in eval_context.model.get_cores():
                    if eval_context.topology.has_edge((c, first)):
                        eval_context.topology.del_edge((c, first))
                        num += 1
                assert num == 1
                # Add new one
                eval_context.topology.add_edge((last, first),
                                               eval_context.model.graph.edge_weight((last, first)))

                # the first core now is busy for longer
                self.log_idle[last] = l_time + t_send

                # the receiving core is done earlier
                _first_new = l_time + t_send + t_receive + T_PROPAGATE

                # Floating point comparison - make sure the two ways
                # of calculating are (approximately) the same
                c1 = self.log_first_message[first] - (slack-cost_direct)
                c2 = _first_new
                assert abs(c1-c2) < 1.0

                self.log_first_message[first] = _first_new

                print 'slack: %2d %2d %10.2f %10.2f %5s' % \
                    (first, last, slack, cost_direct, 'yes' if optimize else 'no')

            else:
{'fraction_non_alphanumeric': 0.08457914024780408, 'fraction_numerical': 0.008667325926356814, 'mean_word_length': 1.8397753551370994, 'pattern_counts': {'":': 0, '<': 12, '<?xml version=': 0, '>': 17, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 4, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '6662724', 'n_tokens_mistral': 4901, 'n_tokens_neox': 4508, 'n_words': 1519}