longest path, route and node structures, but no visited array

gistfile1.lisp

;;; optimizations copyright Rainer Joswig, 2014, joswig@lisp.de
;;; Original: https://github.com/logicchains/LPATHBench/blob/master/writeup.md

;;; Structure declarations

;; In Common Lisp the slot declarations might save space for some types. But
;; that might not make it faster, since access gets more complicated..
;; It also might take more time, when type checks are done at runtime.
;; Some implementations check slot updates for correct types under some
;; SAFETY optimization values.

(defstruct route
  (dest 0 :type fixnum)
  (cost 0 :type fixnum)))

(defstruct node
  (visited    nil :type boolean)
  (neighbours nil :type list))

;;; Setup

;; Here we are parsing from a string, without splitting the string.
;; We could actually use something similar and parse from the input stream.
;; PARSE-INTEGER returns two values: the number parsed and the position behind the number.

(defun parse-line (line &aux (pos 0) n)
  (declare (ignorable n))
  (loop repeat 3
        collect (multiple-value-setq (n pos)
                    (parse-integer line :start pos :junk-allowed t))))

(defparameter *file* "agraph")

;; Reading lines in with READ-LINE is kind of slow, since it conses a new string for each
;; line. For large text files it makes sense to have a more efficient version,
;; which would use a line buffer. Here it is sufficient.

(defun read-places ()
  (with-open-file (stream *file*)
    (let ((num-lines (parse-integer (read-line stream nil))))
      (values (loop for line = (read-line stream nil nil)
                    while line
                    collect (parse-line line))
              num-lines))))

;; When creating an array, the initial contents can be passed as a list. Here
;; we create the array and use MAP-INTO to set the contents (proposal by Svante).
;; Giving it an element type is basically useless. A general array will be created anyway.
;; Structure NODEs will not be inlined. It will be an array of pointers to NODE records.
;; To keep neighbour routes it does not make sense to have an adjustable array. Lists are sufficient.
;; The LOOP usage also shows destructuring of lists.

(defun parse-places ()
  (multiple-value-bind (place-data num-nodes)
      (read-places) 
    (let ((nodes (map-into (make-array num-nodes :element-type 'node)
                           #'make-node)))
      (loop for (node-id neighbour-id dist) in place-data
            do (push (make-route :dest neighbour-id :cost dist)
                     (node-neighbours (elt nodes node-id))))
      nodes)))

;;; Function to be benchmarked

;; we can declare types of functions: types of arguments and the return types.

(declaim (ftype (function (simple-vector node) fixnum)
                get-longest-path))

;; The declarations of optimization are only local in the function to be benchmarked.
;; Keep these declarations as local as possible. Safety zero, means safety zero.

;; With THE we can define types for expression results.

;; Shows also mildly advanced LOOP usage. LispWorks gets the type declaration
;; for the maximized value right.

;; Here we also pass nodes records around, not node-ids.

;; Simple vectors have efficient access. AREF will be basically SVREF.

(defun get-longest-path (nodes node)
  (declare (optimize (speed 3) (space 0) (debug 0) (safety 0)
                     (compilation-speed 0)
                     #+lispworks (fixnum-safety 0))
	   (type simple-vector nodes)
           (type node node))
  (setf (node-visited node) t)
  (loop for neighbour-route of-type route in (node-neighbours node)
        for dest-node = (aref nodes (route-dest neighbour-route))
        unless (node-visited dest-node)
        maximize (the fixnum
                      (+ (the fixnum (route-cost neighbour-route))
                         (the fixnum (get-longest-path nodes dest-node))))
        into max-dist #+lispworks fixnum
        finally
        (setf (node-visited node) nil)
        (return max-dist)))

;;; Main routine, also calculates the runtime

;; don't use DEFPARAMETER for local variables. LET* is fine.

;; We want to display milliseconds, but don't assume that the time values are milliseconds.
;; Common Lisp provides the variable INTERNAL-TIME-UNITS-PER-SECOND.

(defun run ()
  (let* ((nodes    (parse-places))
         (start    (get-internal-real-time))
         (len      (get-longest-path nodes (aref nodes 0)))
         (end      (get-internal-real-time))
         (duration (truncate (* (- end start) 1000)
                             internal-time-units-per-second)))
    (format t "~d LANGUAGE Lisp ~d ~%" len duration)))

#+sbcl
(sb-ext:save-lisp-and-die "lisp" :toplevel #'run :executable t)